本页使用了标题或全文手工转换

克鲁斯克尔演算法

维基百科,自由的百科全书
跳到导航 跳到搜索
克鲁斯克尔演算法
克鲁斯克尔算法的图解
分类 最小生成树
数据结构 并查集
平均时间复杂度
空间复杂度

Kruskal演算法是一種用來尋找最小生成樹的演算法,由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法Boruvka演算法等。三種演算法都是贪心算法的應用。和Boruvka演算法不同的地方是,Kruskal演算法在圖中存在相同權值的邊時也有效。

步驟[编辑]

  1. 新建圖G,G中擁有原圖中相同的節點,但沒有邊
  2. 將原圖中所有的邊按權值從小到大排序
  3. 從權值最小的邊開始,如果這條邊連接的兩個節點於圖G中不在同一個連通分量中,則添加這條邊到圖G中
  4. 重複3,直至圖G中所有的節點都在同一個連通分量中

證明[编辑]

  1. 這樣的步驟保證了選取的每條邊都是橋,因此圖G構成一個樹。
  2. 為什麼這一定是最小生成樹呢?關鍵還是步驟3中對邊的選取。演算法中總共選取了n-1條邊,每條邊在選取的當時,都是連接兩個不同的連通分量的權值最小的邊
  3. 要證明這條邊一定屬於最小生成樹,可以用反證法:如果這條邊不在最小生成樹中,它連接的兩個連通分量最終還是要連起來的,通過其他的連法,那麼另一種連法與這條邊一定構成了環,而環中一定有一條權值大於這條邊的邊,用這條邊將其替換掉,圖仍舊保持連通,但總權值減小了。也就是說,如果不選取這條邊,最後構成的生成樹的總權值一定不會是最小的。


時間複雜度[编辑]

平均时间复杂度为,其中分别是图的边集和点集。

例示[编辑]

图例 说明
Kruskal Algorithm 1.svg ADCE是最短的两条边,长度为5,其中AD被任意选出,以高亮表示。
Kruskal Algorithm 2.svg 现在CE是不属于环的最短边,长度为5,因此第二个以高亮表示。
Kruskal Algorithm 3.svg 下一条边是长度为6的DF,同样地以高亮表示。
Kruskal Algorithm 4.svg 接下来的最短边是ABBE,长度均为7。AB被任意选中,并以高亮显示。边BD用红色高亮表示,因为BD之间已经存在一条(标为绿色的)路径,如果选择它将会构成一个环(ABD)。
Kruskal Algorithm 5.svg 以高亮表示下一条最短边BE,长度为7。这时更多的边用红色高亮标出:会构成环BCEBC、会构成环DBEADE以及会构成环FEBADFE
Kruskal Algorithm 6.svg 最终,标记长度为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 所在的子树合并