資料內(nèi)容：

最小生成樹(shù)（Minimum Spanning Tree, MST）
最小生成樹(shù)是一個(gè)無(wú)向加權(quán)連通圖的子集，它連接了圖中的所有頂點(diǎn)（節(jié)點(diǎn)），并且沒(méi)有循環(huán)（回路），同
時(shí)所有邊的權(quán)重之和是最小的。在計(jì)算機(jī)網(wǎng)絡(luò)、電路設(shè)計(jì)、物流運(yùn)輸?shù)阮I(lǐng)域有著廣泛的應(yīng)用。
Kruskal算法實(shí)現(xiàn)原理和步驟
1. 將圖中的所有邊按照權(quán)重從小到大排序。
2. 從權(quán)重最小的邊開(kāi)始，如果這條邊連接的兩個(gè)頂點(diǎn)不屬于同一個(gè)集合（通過(guò)并查集來(lái)判斷），則將其加
入最小生成樹(shù)，并合并這兩個(gè)頂點(diǎn)的集合。
3. 重復(fù)步驟2，直到選擇的邊的數(shù)量等于圖中的頂點(diǎn)數(shù)減一。
Python實(shí)現(xiàn)

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
# 按照權(quán)重排序所有的邊
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)
# 如果邊的兩個(gè)頂點(diǎn)不屬于同一個(gè)集合（即沒(méi)有形成環(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}")