prim和kruscal算法得到的最小生成树是否一样

显示全部楼层 · 2011-7-25 18:11:00

prim和 kruscal 的算法思想是什么了的。请再解释下。

千问 · 2011-7-25 18:11:00

应该不一样。可以用一个图根据两算法试一下，若一样，再修改图，之后应该就可以了。（百度或者查书本更加有效……）构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。Kruskal算法构造G的最小生成树：将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v, w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v, w)将T1和T2连接成一...

千问 · 2011-7-25 18:11:00

不唯一.如果最小生成树不唯一则用不同的算法就不唯一.关键路径是不会变的.非关键的可选路径是会变的.比如2.3和1.4.有可能1,4和2,3 .如果都是四个都2.任意选都是2.结果显然不一样.当然.这个和初态有关...

千问 · 2011-7-25 18:11:00

算法的思想应该是贪心，你要说是A*也可以...