Python 算法：最小生成树（Kruskal 算法）

# /*
# Python 算法：最小生成树（Kruskal 算法）
# --------------------------------------------------------
# 原理概要：
# Kruskal 属于贪心算法，通过“从小到大选边”的方式生成最小生成树。
#
# 基本步骤：
# 1) 将图中所有边按权值从小到大排序；
# 2) 依次取最小边，如果加入后不产生环，则加入 MST；
# 3) 使用并查集（Union-Find）判断是否成环；
# 4) 直到 MST 包含 (顶点数 - 1) 条边。
#
# 适合场景：
# - 稀疏图效果优于 Prim 的矩阵实现
# - 边较少但权值不均的情况效率更高
# */

# --------------------------------------------------------
# 并查集（Union-Find）实现
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    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:
            # 按秩合并
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

# --------------------------------------------------------
# Kruskal 主算法
def kruskal_mst(vertices, edges):
    """
    vertices: 顶点数量
    edges: 边列表 (u, v, weight)
    """
    # 1) 边按权值排序
    edges = sorted(edges, key=lambda x: x[2])

    uf = UnionFind(vertices)
    mst = []

    # 2) 从小到大选边
    for u, v, w in edges:
        if uf.union(u, v):     # 能加入 MST（无环）
            mst.append((u, v, w))

        if len(mst) == vertices - 1:
            break

    return mst

# --------------------------------------------------------
# 示例图：边列表 (u, v, weight)
edges = [
    (0, 1, 2),
    (0, 3, 6),
    (1, 2, 3),
    (1, 3, 8),
    (1, 4, 5),
    (2, 4, 7),
    (3, 4, 9)
]

vertices = 5

# 执行 Kruskal
mst = kruskal_mst(vertices, edges)

# 显示结果
print("最小生成树边列表 (u, v, weight)：")
for e in mst:
    print(e)

# --------------------------------------------------------
# 输出示例（顺序可能不同，但结构一致） (u, v, weight)：
# (0, 1, 2)
# (1, 2, 3)
# (1, 4, 5)
# (0, 3, 6)
#
# Kruskal 要点总结：
# - 利用“排序 + 并查集”实现；
# - 最适合边稀疏的图；
# - 时间复杂度 O(E log E)；
# - 保证不会形成环；
# */