题目描述

Q：为什么不同于kruskal ， 判断孤立点 在循环内部判断？
A：因为kruskal 是基于边来枚举，而prim是基于点来枚举。prim算法中如果更新得到的点是距离为无穷，或者说，这个点不能被更新到，那么一定不能构成最小生成树。反过来说，如果像krukal一样，选择了n个点不能说明，一定能连通。而kruskal算法，选择了n-1条边，在已知是n个节点的情况下，一定是连通的。

Python 代码

N = 550
M = 100010
inf = float("inf")
h = [-1]*N
e = [0]*M*2
ne = [0]*M*2
w = [0]*M*2
idx = 0
state = [False]*N
dist = [inf]*N
def add(x,y,z):
    global idx
    ne[idx] = h[x]
    e[idx] = y
    w[idx] = z
    h[x] = idx
    idx += 1

if __name__ == '__main__':
    n,m = map(int,input().split())
    for _ in range(m):
        u,v,k = map(int,input().split())
        add(u,v,k)
        add(v,u,k)


    dist[1] = 0 
    ans  = 0
    for _ in range(n):
        temp = 0
        for i in range(1,n+1):
            if state[i] is False and dist[temp]>dist[i]:
                temp = i
        if dist[temp] == inf:
            print("impossible")
            exit()
        state[temp] = True

        ans += dist[temp]
        head = h[temp]
        while head!= -1:
            node = e[head]
            weight = w[head]
            if state[node] is False and dist[node]>weight:
                dist[node] = weight
            head = ne[head]


    print(ans)