克鲁斯克尔演算法
Kruskal演算法是一種用來尋找最小生成樹的演算法[1],由Joseph Kruskal在1956年發表[2]。用來解決同樣問題的還有Prim演算法和Boruvka演算法等。三種演算法都是贪心算法的應用。和Boruvka演算法不同的地方是,Kruskal演算法在圖中存在相同權值的邊時也有效。
克鲁斯克尔演算法 | |
---|---|
概况 | |
類別 | 最小生成树 |
資料結構 | 并查集 |
复杂度 | |
平均時間複雜度 | |
空間複雜度 | |
相关变量的定义 |
图与树 搜索算法 |
---|
分类 |
|
相关主题 |
步骤
- 新建图,中拥有原图中相同的节点,但没有边
- 将原图中所有的边按权值从小到大排序
- 从权值最小的边开始,如果这条边连接的两个节点于图中不在同一个连通分量中,则添加这条边到图中
- 重複3,直至图中所有的节点都在同一个连通分量中
证明
- 这样的步骤保证了选取的每条边都是桥,因此图构成一个树。
- 为什麽这一定是最小生成树呢?关键还是步骤3中对边的选取。演算法中总共选取了条边,每条边在选取的当时,都是连接两个不同的连通分量的权值最小的边
- 要证明这条边一定属于最小生成树,可以用反证法:如果这条边不在最小生成树中,它连接的两个连通分量最终还是要连起来的,通过其他的连法,那麽另一种连法与这条边一定构成了环,而环中一定有一条权值大于这条边的边,用这条边将其替换掉,图仍旧保持连通,但总权值减小了。也就是说,如果不选取这条边,最后构成的生成树的总权值一定不会是最小的。
時間複雜度
平均时间复杂度为,其中和分别是图的边集和点集。
示例
图例 | 说明 |
---|---|
AD和CE是最短的两条边,长度为5,其中AD被任意选出,以高亮表示。 | |
现在CE是不属于环的最短边,长度为5,因此第二个以高亮表示。 | |
下一条边是长度为6的DF,同样地以高亮表示。 | |
接下来的最短边是AB和BE,长度均为7。AB被任意选中,并以高亮表示。边BD用红色高亮表示,因为B和D之间已经存在一条(标为绿色的)路径,如果选择它将会构成一个环(ABD)。 | |
以高亮表示下一条最短边BE,长度为7。这时更多的边用红色高亮标出:会构成环BCE的BC、会构成环DBEA的DE以及会构成环FEBAD的FE。 | |
最终,标记长度为9的边EG,得到最小生成树,结束算法过程。 |
伪代码
KRUSKAL-FUNCTION(G, w) 1 F := 空集合 2 for each 图 G 中的顶点 v 3 do 將 v 加入森林 F 4 所有的边(u, v) ∈ E依权重 w 递增排序 5 for each 边(u, v) ∈ E 6 do if u 和 v 不在同一棵子树 7 then F := F ∪ {(u, v)} 8 將 u 和 v 所在的子树合并
参考文献
- Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein. Third. MIT Press. 2009: 631. ISBN 978-0262258104.
- Kruskal, J. B. . Proceedings of the American Mathematical Society. 1956, 7 (1): 48–50. JSTOR 2033241. doi:10.1090/S0002-9939-1956-0078686-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.