資料內容：

最小生成樹（Minimum Spanning Tree, MST）
最小生成樹是一個無向加權連通圖的子集，它連接了圖中的所有頂點（節(jié)點），并且沒有循環(huán)（回路），同
時所有邊的權重之和是最小的。在計算機網絡、電路設計、物流運輸等領域有著廣泛的應用。
Kruskal算法實現原理和步驟
1. 將圖中的所有邊按照權重從小到大排序。
2. 從權重最小的邊開始，如果這條邊連接的兩個頂點不屬于同一個集合（通過并查集來判斷），則將其加
入最小生成樹，并合并這兩個頂點的集合。
3. 重復步驟2，直到選擇的邊的數量等于圖中的頂點數減一。
Python實現

class UnionFind:
def __init__(self, vertices):
self.parent = {v: v for v in range(vertices)}
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
self.parent[rootX] = rootY
class Graph:
def __init__(self, vertices):
self.V = vertices
self.edges = []
def add_edge(self, u, v, w):
self.edges.append([u, v, w])
def kruskal_mst(self):
result = []
i, e = 0, 0
# 按照權重排序所有的邊
self.edges.sort(key=lambda item: item[2])
uf = UnionFind(self.V)
while e < self.V - 1:
u, v, w = self.edges[i]
i += 1
x = uf.find(u)
y = uf.find(v)
# 如果邊的兩個頂點不屬于同一個集合（即沒有形成環(huán)）
if x != y:
e += 1
result.append([u, v, w])
uf.union(x, y)
return result
# 示例
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
result = g.kruskal_mst()
print("Edges in the constructed MST")
for u, v, weight in result:
print(f"{u} -- {v} == {weight}")