Java版-图论-最小生成树-Prim算法

实现描述

如图：

Prim算法的基本思想是从一个顶点开始，逐步构建最小生成树。具体步骤如下：

1. 随机选取一个顶点作为起始点，并将其加入最小生成树的集合中。
2. 从该顶点出发，选择一条边连接到其他未被访问的顶点中的最小权值边。
3. 将该顶点加入到最小生成树的集合中，并标记为已访问。
4. 重复步骤2和步骤3，直到最小生成树包含所有顶点。

与Kruskal算法相比，Kruskal是选择最小边，通过判断连通性加入最小生成树；
Prim算法是选择点，构成最小生成树，然后选择未加入的点，通过权重判断是否能加入最小生成树；

下面是详细的构建过程：

首先加入index=0的点，此时最小生成树包含了只有0；

最小生成树此时节点[0],其他各个节点到最小生成树距离表：

索引	minDistance（所有节点到最小生成树的最小距离）	nodeInTheTree（记录节点是否在最小生成树里面）
0		true
1	5	false
2	8	false
3	7	false
4	无穷大	false
5	3	false

之后，选择距离最小生成树距离最近的点加入，这里选择index=5,最小生成树此时节点[0,5],其他各个节点到最小生成树距离表：

索引	minDistance（所有节点到最小生成树的最小距离）	nodeInTheTree（记录节点是否在最小生成树里面）
0		true
1	5	false
2	8	false
3	6	false
4	1	false
5	3	true

注意，此时最小生成树节点[0,5]，是两个，这两个是一个整体；

依次类推，直至nodeInTheTree数组里面所有节点都加入，然后计算minDistance节点的和即为最小生成树边距离；

注意，如果需要获取加入的起点-终点的边情况，额外添加记录数组parents，当获取到本次加入最小生成树的节点时候，更新其他点连入最小生成树的边情况进行记录；

实现代码

public static void main(String[] args) {int nodeNum = 6;int[][] grid = {{0, 1, 5},{0, 5, 3},{0, 3, 7},{0, 2, 8},{1, 2, 4},{2, 5, 9},{3, 5, 6},{2, 3, 5},{3, 4, 5},{4, 5, 1}};int[][] matrix = new int[nodeNum][nodeNum]; // init matrixfor (int i = 0; i < nodeNum; i++) {Arrays.fill(matrix[i], Integer.MAX_VALUE);}for (int i = 0; i < grid.length; i++) {int u = grid[i][0];int v = grid[i][1];int w = grid[i][2];matrix[u][v] = w;matrix[v][u] = w;}int[] minDistance = new int[nodeNum]; // 所有节点到最小生成树的最小距离Arrays.fill(minDistance, Integer.MAX_VALUE);boolean[] nodeInTheTree = new boolean[nodeNum]; //记录节点是否在最小生成树里面int[] parents = new int[nodeNum]; //记录最小生成树的边Arrays.fill(parents, -1);for (int i = 0; i < nodeNum; i++) {int current = 0; //默认0int minValue = Integer.MAX_VALUE;//选择距离当前生成树最近的点for (int j = 0; j < nodeNum; j++) {if (nodeInTheTree[j]) {//在树中跳过continue;}if (minDistance[j] < minValue) {current = j;minValue = minDistance[j];}}nodeInTheTree[current] = true;//将选择的节点加入最小生成树//更新其他节点到最小生成树的距离for (int j = 0; j < nodeNum; j++) {if (nodeInTheTree[j]) {//在树中跳过continue;}if (matrix[current][j] < minDistance[j]) {minDistance[j] = matrix[current][j];parents[j] = current;     //用最新选择的点去连接之前的点}}}int totalDistance = 0;for (int i = 1; i < nodeNum; i++) {totalDistance += minDistance[i];}System.out.println("总的权重值为：" + totalDistance);//输出边for (int i = 1; i < nodeNum; i++) {System.out.println("u=" + i + "; v=" + parents[i]);}}