【代码随想录算法训练营第六十二天|卡码网53.寻宝（prim算法和kruskal算法）】

53.寻宝

prim算法

prim算法三部曲：
1.选择当前最短入树结点；2.更新入树结点；3.更新结点距离最小生成树的距离。
可以把所有已经使用过的结点看作一个整体，然后把他们相接的结点的结点顶点边中进行选择，选择最短的一条边把该结点入树，某种程度来说也是一种贪心？

V, E = map(int, input().split())
nodes = [[float('inf')] * (V+1) for _ in range(V+1)]
for i in range(E):start, end, length = map(int, input().split())nodes[start][end] = lengthnodes[end][start] = lengthvisited = [False] * (V+1)
minDist = [float('inf')] * (V+1)cur = 1 
for i in range(V-1):minD = float('inf')# 1.选择最短入树结点for j in range(1, V+1):if not visited[j] and minDist[j]<minD:cur = jminD = minDist[j]# 2.入树visited[cur] = True# 3.更新相接不在树中的顶点的距离for i in range(1, V+1):if not visited[i] and nodes[cur][i] < minDist[i]:minDist[i] = nodes[cur][i]
result = 0
for i in range(2, V+1):result += minDist[i]
print(result)

kruskal算法

kruskal算法以边为导向，先把边按照长度从小到大排序，然后一个个检查边的两个端点是否在同一个集合中（这里使用并查集判断），在同一个集合中就不加入这个边，不在的话就加入。

V, E = map(int, input().split())
edges = []
for i in range(E):edges.append(list(map(int, input().split())))
edges.sort(key= lambda edge: edge[2])father = [0] * (V+1)
for i in range(V+1):father[i] = idef find(u):if father[u] != u:father[u] = find(father[u])return father[u]def isSame(u, v):u = find(u)v = find(v)return u == vdef join(u, v):u = find(u)v = find(v)if not u==v:father[v] = uresult = 0
for edge in edges:start = edge[0]end = edge[1]val = edge[2]if not isSame(start, end):result += valjoin(start, end)
print(result)