克鲁斯克尔演算法
维基百科,自由的百科全书
Kruskal演算法是一種用來尋找最小生成樹的演算法,由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法。
[编辑] 步骤
- 新建图G,G中拥有原图中相同的节点,但没有边
- 将原图中所有的边按权值从小到大排序
- 从权值最小的边开始,如果这条边连接的两个节点于图G中不在同一个连通分量中,则添加这条边到图G中
- 重复3,直至图G中所有的节点都在同一个连同分量中
这样的步骤保证了选取的每条边都是桥,因此图G构成一个树。为什么这一定是最小生成树呢?关键还是步骤3中对边的选取。 算法中总共选取了n-1条边,每条边在选取的当时,都是连接两个不同的连通分量的权值最小的边,要证明这条边一定属于最小生成树,可以用反证法: 如果这条边不在最小生成树中,它连接的两个连通分量最终还是要连起来的,通过其它的连法,那么另一种连法与这条边一定构成了环,而环中一定有一条权值大于这条边的边,用这条边将其替换掉,图仍旧保持连通,但总权值减小了。也就是说,如果不选取这条边,最后构成的生成树的总权值一定不会是最小的。
[编辑] 实现
KRUSKAL-FUNCTION(G, w) 1 F := 空集合 2 for each 圖 G 中的頂點 v 3 do 將 v 加入森林 F 4 所有的邊依權重 w 遞增排序 5 for each 邊 6 do if u 和 v 不在同一棵子樹 7 then F := F U {(u, v)} 8 將 u 和 v 所在的子樹合併