用Python写一个图算法之最小生成树算法含注释说明

以下是使用Prim算法实现最小生成树的代码：

from typing import List, Tuple

def prim_algorithm(graph: List[List[Tuple[int, int]]]) -> List[Tuple[int, int]]:
    """
    Prim算法实现最小生成树

    参数:
        graph: 无向图的邻接表表示法，graph[i]表示与节点i相邻的节点列表，(j, w)表示节点i到节点j的边权重为w

    返回值:
        以元组形式表示的最小生成树，元组中第一个值表示边的起始节点，第二个值表示边的结束节点，例如：[(0, 1), (1, 2), (2, 3)]
    """
    n = len(graph)  # 图中节点的个数
    mst = []  # 存储最小生成树的边
    selected = set([0])  # 存储已经被选中的节点的集合
    candidates = graph[0]  # 存储候选边的集合，初始时为节点0的所有邻接边
    while len(selected) < n:
        min_edge = None  # 选出当前候选边中权重最小的边
        for edge in candidates:
            if edge[0] not in selected:  # 如果边的起始节点不在已选节点集合中，则不考虑该边
                continue
            if min_edge is None or edge[1] < min_edge[1]:  # 如果该边权重小于目前最小边，则更新最小边
                min_edge = edge
        mst.append(min_edge)  # 将最小边加入到最小生成树中
        selected.add(min_edge[1])  # 将该边的结束节点加入到已选节点集合中
        candidates.extend(graph[min_edge[1]])  # 将该边的结束节点的所有邻接边加入到候选边集合中
        candidates = [edge for edge in candidates if edge[0] in selected]  # 过滤掉候选边集合中已经不合法的边
    return mst

这个算法的时间复杂度是 $O(E log V)$，其中 $E$ 表示图中的边数，$V$ 表示图中的节点数。