Kruskal演算法

[编辑] 步骤

1. 新建图G，G中拥有原图中相同的节点，但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
4. 重复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 所在的子樹合併

“Kruskal演算法”是一个關於數學、还没写完的小作品，希望您能继续编辑或者是修订这个条目。