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

1个回答

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