DSA Kruskal 演算法
Kruskal 演算法
Kruskal 演算法查詢無向圖中的最小生成樹 (MST)，或最小生成森林。
Kruskal 演算法找到的 MST（或 MSTs）是連線所有頂點（或儘可能多）且總邊權重最小的邊集。
Kruskal 演算法按從小到大的邊權重順序新增邊到 MST（或最小生成森林）。
會形成環的邊不會被新增到 MST 中。這些是上面動畫中的紅色閃爍線。
Kruskal 演算法會檢查圖中的所有邊，但上面的動畫會在 MST 或最小生成森林完成時停止，這樣您就不必等待最長的邊被檢查。
最小生成森林 當圖中存在多個最小生成樹時，就稱之為最小生成森林。當圖不連通時就會發生這種情況。在上面的動畫中，您可以嘗試透過使用複選框來驗證這一點。
與 Prim 演算法不同，Kruskal 演算法可用於不連通的圖，這意味著它可以找到多個 MST，這就是我們稱之為最小生成森林的原因。
為了確定一條邊是否會形成環，我們將在 Kruskal 演算法中使用 並查集（Union-Find）環檢測。
工作原理
- 將圖中的邊按從小到大的邊權重排序。
- 對於每條邊，從權重最小的邊開始
- 這條邊會在當前的 MST 中形成環嗎？
- 如果否：將邊新增為 MST 邊。
- 這條邊會在當前的 MST 中形成環嗎？
手動演練
讓我們在下面的圖上手動執行 Kruskal 演算法，以便在嘗試程式設計之前理解詳細的逐步操作。
前三條邊被新增到 MST 中。這三條邊具有最小的邊權重且不形成任何環。
- C-E，權重 2
- D-E，權重 3
- A-B，權重 4
之後，邊 C-D（圖中紅色標出）無法新增，因為它會形成一個環。
Kruskal 演算法接下來嘗試新增到 MST 的四條邊是：
- E-G，權重 6
- C-G，權重 7（未新增）
- D-F，權重 7
- B-C，權重 8
邊 C-G（圖中紅色標出）無法新增到 MST，因為它會形成一個環。
正如您所見，此時 MST 已經建立完成，但 Kruskal 演算法將繼續執行，直到所有邊都被測試是否可以新增到 MST 中。
Kruskal 演算法嘗試新增到 MST 的最後三條邊是邊權重最高的邊：
- A-C，權重 9（未新增）
- A-G，權重 10（未新增）
- F-G，權重 11（未新增）
這些邊中的每一條都會在 MST 中形成一個環，所以它們無法新增。
Kruskal 演算法現在已完成。
執行下面的模擬，檢視 Kruskal 演算法如何執行我們剛剛完成的手動步驟。
注意： 儘管 Kruskal 演算法會檢查圖中的所有邊，但此頁面頂部的動畫會在新增完最後一條 MST 或最小生成森林的邊後立即停止，這樣我們就不必檢視所有無法新增的紅色邊。
這是可能的，因為對於連通圖，只有一個 MST，並且當 MST 中的邊數比圖中的頂點數少 1 時（\(V-1\)），搜尋就可以停止。對於不連通的圖，我們的動畫中有兩個 MST，當 MST 的總邊數達到 \(V-2\) 時，演算法會停止。
Kruskal 演算法的實現
為了讓 Kruskal 演算法找到最小生成樹 (MST) 或最小生成森林，我們建立一個 Graph 類。稍後我們將使用這個 Graph 類中的方法來從上面的示例建立圖，並在其上執行 Kruskal 演算法。
class Graph:
def __init__(self, size):
self.size = size
self.edges = [] # For storing edges as (weight, u, v)
self.vertex_data = [''] * size # Store vertex names
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.edges.append((weight, u, v)) # Add edge with weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 8 行和第 12 行： 檢查輸入引數 u、v 和 vertex 是否在可能的索引值範圍內。
為了在 Kruskal 演算法中進行並查集環檢測，這兩個方法 find 和 union 也在 Graph 類中定義。
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1第 15-18 行： find 方法使用 parent 陣列遞迴查詢頂點的根。對於每個頂點，parent 陣列儲存一個指向該頂點父節點的指標（索引）。當 find 方法找到 parent 陣列中指向自身的一個頂點時，就找到了根頂點。請繼續閱讀，瞭解 find 方法和 parent 陣列如何在 kruskals_algorithm 方法中使用。
第 20-29 行： 當一條邊被新增到 MST 時，union 方法使用 parent 陣列來合併（union）兩個樹。 rank 陣列儲存了每個根頂點的樹高度的粗略估計。合併兩棵樹時，秩較低的根會成為另一棵樹的根節點的子節點。
以下是 Kruskal 演算法作為 Graph 類中的方法實現的方式：
def kruskals_algorithm(self):
result = [] # MST
i = 0 # edge counter
self.edges = sorted(self.edges, key=lambda item: item[2])
parent, rank = [], []
for node in range(self.size):
parent.append(node)
rank.append(0)
while i < len(self.edges):
u, v, weight = self.edges[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
result.append((u, v, weight))
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, weight in result:
print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")第 35 行： Kruskal 演算法在嘗試將邊新增到 MST 之前，必須先對邊進行排序。
第 40-41 行： 初始化 parent 和 rank 陣列。開始時，每個頂點都是自己的根（parent 陣列中的每個元素都指向自身），並且每個頂點的初始高度為 0（rank 陣列中的值為 0）。
第 44-45 行： 選擇最小的邊，並將 i 加 1，以便在下一次迭代中選擇正確的邊。
第 47-51 行： 如果當前邊的兩個端點 u 和 v 具有不同的根 x 和 y，則表示新邊不會形成環，並且將合併這兩個樹。為了合併樹，當前邊被新增到 result 陣列中，然後執行 union 方法以確保樹被正確合併，從而使合併後的結果樹只有一個根頂點。
現在，讓我們建立“手動執行”上面顯示的圖，並在其上執行 Kruskal 演算法。
示例
Python
class Graph:
def __init__(self, size):
self.size = size
self.edges = [] # For storing edges as (weight, u, v)
self.vertex_data = [''] * size # Store vertex names
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.edges.append((u, v, weight)) # Add edge with weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskals_algorithm(self):
result = [] # MST
i = 0 # edge counter
self.edges = sorted(self.edges, key=lambda item: item[2])
parent, rank = [], []
for node in range(self.size):
parent.append(node)
rank.append(0)
while i < len(self.edges):
u, v, weight = self.edges[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
result.append((u, v, weight))
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, weight in result:
print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(0, 1, 4) #A-B, 4
g.add_edge(0, 6, 10) #A-G, 10
g.add_edge(0, 2, 9) #A-C, 9
g.add_edge(1, 2, 8) #B-C, 8
g.add_edge(2, 3, 5) #C-D, 5
g.add_edge(2, 4, 2) #C-E, 2
g.add_edge(2, 6, 7) #C-G, 7
g.add_edge(3, 4, 3) #D-E, 3
g.add_edge(3, 5, 7) #D-F, 7
g.add_edge(4, 6, 6) #E-G, 6
g.add_edge(5, 6, 11) #F-G, 11
print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()Kruskal 演算法的時間複雜度
有關時間複雜度的一般性解釋，請訪問此頁面。
令 \(E\) 為圖中邊的數量，Kruskal 演算法的時間複雜度為：
\[ O( E \cdot log{E} ) \]
我們得到這個時間複雜度是因為在 Kruskal 開始新增邊到 MST 之前，必須先對邊進行排序。使用像 快速排序 或 歸併排序 這樣的快速排序演算法，僅此排序本身的時間複雜度為 \( O( E \cdot log{E} ) \)。
在對邊進行排序之後，它們會逐一被檢查，以確定是否會形成環，如果不會，則將其新增到 MST 中。
儘管使用 find 方法檢查環的建立以及使用 union 方法將邊包含到 MST 中看起來工作量很大，但這些仍然可以視為一個操作。之所以可以將它們視為一個操作，是因為它們花費的時間大約是常數時間。這意味著此操作所需的時間隨著圖的增長而增長非常緩慢，因此實際上不會影響整體時間複雜度。
由於 Kruskal 演算法的時間複雜度僅隨邊的數量 \(E\) 而變化，因此它對於稀疏圖（其中邊數 \(E\) 與頂點數 \(V\) 的比率相對較低）尤其快速。
