最小生成树（Minimum Spanning Tree, MST）
最小生成树是一个无向加权连通图的子集，它连接了图中的所有顶点（节点），并且没有循环（回路），同
时所有边的权重之和是最小的。在计算机网络、电路设计、物流运输等领域有着广泛的应用。
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)
# 如果边的两个顶点不属于同一个集合（即没有形成环）
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}")