最小生成树prim算法

这里有一个无向图, 求其最小生成树

对应的图G的邻接矩阵g为 (INF 为无穷)

0123456780010INFINF11INFINFINFINF11001812INF12INFINFINF2INF180INFINF6INF8INF3INF12INF09INF10INFINF411INFINF90INFINFINF45INF126INFINF0INF7INF6INFINFINF10INFINF0467INFINF8INFINF74058INFINFINFINF4INF650

假设从0开始生成最小生成树 初始化构造一个最小代价的数组

int[] lowcost = g[0];

表示从0到各个节点的代价, 去掉多余的变表示为

遍历剩余8个节点, 找到从0出发代价最小的节点

min = INF; for(int i=1; i<9;i++) { if(lowcost[i] != 0 && lowcost[i] < min) { min = lowcost[i]; k = i; // 记录下那个是最小的节点 } } // 到k的代价置为0, 后续不用计算 lowcost[k] = 0;

节点0能够到达1, 4 代价分别为10, 11, 所以最终k为1

找到了1节点, 然后计算其他节点到1节点的代价, 如果发现2,3,4,5,6,7,8节点到1的代价小于到0的代价, 那么我们更新我们的最小代价数组

for(int i=1; i<9; i++) { if(lowcost[i] !=0 && g[k][i] < lowcost[i]) { lowcost[i] = g[k][i] } }

表示成图如下所示: 到目前为止, 我们的lowcost根据节点0, 节点1构造出来一个已知的最小代价数组, 然后我们从最小代价数组中再找一个最小代价的节点, 表示为节点0/节点1到某个节点的最小代价, 计算得到 到4的代价最小, 然后我们再计算4到其他节点的代价, 更新lowcost, 得到下图结果 同理8最小

7最小

6最小

5最小

2最小

3最小

完整算法

public class Prim { private static final int INF = 10000; public static void main(String[] args) { int[][] g = new int[][]{ {0 , 10 , INF , INF , 11 , INF , INF , INF , INF }, {10 , 0 , 18 , 12 , INF , 12 , INF , INF , INF }, {INF , 18 , 0 , INF , INF , 6 , INF , 8 , INF }, {INF , 12 , INF , 0 , 9 , INF , 10 , INF , INF }, {11 , INF , INF , 9 , 0 , INF , INF , INF , 4 }, {INF , 12 , 6 , INF , INF , 0 , INF , 7 , INF }, {INF , INF , INF , 10 , INF , INF , 0 , 4 , 6 }, {INF , INF , 8 , INF , INF , 7 , 4 , 0 , 5 }, {INF , INF , INF , INF , 4 , INF , 6 , 5 , 0 } }; int[] lowcost = g[0]; int[] adjvex = new int[g.length]; for(int i=1; i<g.length; i++){ int min = 10000000; int k = 0; for (int j = 0; j < g.length; j++) { if(lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; // 记录下那个是最小的节点 } } // 打印下到k的最小代价 的邻接点 System.out.println(adjvex[k] + "->" + k); lowcost[k] = 0; for(int j=1; j<g.length; j++) { if(lowcost[j] !=0 && g[k][j] < lowcost[j]) { lowcost[j] = g[k][j]; // j节点现在唯一连通到k 且是最小代价 adjvex[j] = k; //这里记录下j的邻接点k } } } } }