Prim算法 最小生成树问题

Question

如图所示，用克鲁斯卡尔算法我会求解，但是我用prim算法的时候，从V1出发，依次是V2 -> V7（就是V1正下方的点） -> V6 。重点来了，此时V5并没有被访问过，所以以V6为弧尾的路径只有V5了，显然不对请问1.这里用Prim算法应该怎么做？2.克鲁斯卡尔算法和Prim算法得到的路径一样吗？

Answer 1

你的图里有两条边权重一样，在实际计算前无法事先保证最小生成树的唯一性，即使是两个不同的Prim算法也可能产生不同的结果
当然，计算完之后情况会略有不同，下面会解释

Prim算法首先会依次选
E(1,2)=1
E(2,7)=2
E(2,3)=3
然后E(3,4)=E(7,6)=4，会面临两种选择
如果优先选E(3,4)这条边，那么下一步仍然会选E(7,6)，反过来也一样，所以这个图恰好没影响
继续下去最终得到
E(1,2)=1
E(2,7)=2
E(2,3)=3
E(3,4)=4
E(7,6)=4
E(4,5)=6
这样6条边构成唯一的最小生成树，总权重是20
（唯一性是因为总权重不超过20的其它子图确实都不连通）
既然最小生成树唯一，Kruskal算法当然也会产生同一棵树