生成树算法

一、Prim算法

概论

适合稠密图，不进行堆优化的时间复杂度是\(O(n^2)\)，进行堆优化则是\(O(mlogn)\)
每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小，基于一种贪心的策略。
证明的引理
对于任意切割 (S, V-S)，其中 S 是生成树 T 的节点集合，V-S 是未包含在 T 中的节点集合，存在一条横切边连接 S 和 V-S 中的顶点，并且该边的权重是最小的。

礼貌拿图：@Hasity【https://www.acwing.com/solution/content/38312/】
如果像记录生成树的边的话，可以用一个pre数组，在更新时记录前驱节点！

代码

# prim算法求最小生成树

from math import inf
n,m = map(int,input().split())
g = [[inf] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    u,v,w = map(int,input().split())
    g[u][v] = g[v][u] = min(g[u][v],w)

vis = [False] * (n + 1)
dis = [inf] * (n + 1)

ans = 0
# dis[i]保存的是节点i与已连通树的最短距离
# 首先将1节点作为生成树开始的起点
dis[1] = 0

for _ in range(n):
    t = -1
    # 寻找距离连通部分距离最短的节点将其纳入生成树的范围
    for i in range(1,n + 1):
        if not vis[i] and (t == -1 or dis[t] > dis[i]):
            t = i
    vis[t] = True
    # 如果一个点距离已结成的生成树的距离为inf，那么说明不存在一棵树将所有点串起来
    if dis[t] == inf:
        print("impossible")
        exit()
    # 加 上 那 条 边
    ans += dis[t]
    # 用新加入t点去更新剩余的点到生成树的最小距离！
    for j in range(1,n + 1):
        if dis[j] > g[t][j]:
            dis[j] = g[t][j]
print(ans)