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

# /*
# Python 算法：最小生成树（Prim 算法）
# --------------------------------------------------------
# 原理：
# Prim 算法是一种贪心算法，用于求解带权无向图的最小生成树（MST）。
# 步骤：
# 1) 从任意顶点开始，将其加入 MST 集合；
# 2) 在所有与 MST 相连的边中选择权值最小的边，将该边另一端顶点加入 MST；
# 3) 重复步骤 2，直到所有顶点都在 MST 中。
#
# 适用场景：
# - 无向连通图
# - 需要求最小生成树以减少总成本
# */

import sys

# --------------------------------------------------------
# 示例图（邻接矩阵表示，0 表示无连接）
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

def prim_mst(graph):
    num_vertices = len(graph)
    selected = [False] * num_vertices  # 顶点是否已加入 MST
    selected[0] = True                  # 从顶点 0 开始

    mst_edges = []  # 存储 MST 边 (u, v, weight)

    for _ in range(num_vertices - 1):
        min_weight = sys.maxsize
        u = v = -1
        for i in range(num_vertices):
            if selected[i]:
                for j in range(num_vertices):
                    if not selected[j] and graph[i][j]:
                        if graph[i][j] < min_weight:
                            min_weight = graph[i][j]
                            u, v = i, j
        mst_edges.append((u, v, min_weight))
        selected[v] = True

    return mst_edges

# --------------------------------------------------------
# 演示
mst = prim_mst(graph)
print("最小生成树边列表 (u, v, weight)：")
for edge in mst:
    print(edge)

# --------------------------------------------------------
# 输出示例：
# 最小生成树边列表 (u, v, weight)：
# (0, 1, 2)
# (1, 2, 3)
# (0, 3, 6)
# (1, 4, 5)
#
# 要点总结：
# 1) Prim 算法贪心策略：每次选择连接 MST 的最小边；
# 2) 时间复杂度：
#    - 使用邻接矩阵 O(V^2)
#    - 使用优先队列 + 邻接表 O(E log V)
# 3) 保证生成的树覆盖所有顶点且总权值最小；
# 4) 适合稠密图实现。
# */

#
# 最小生成树边列表 (u, v, weight)：
# (0, 1, 2)
# (1, 2, 3)
# (1, 4, 5)
# (0, 3, 6)