代码随想录算法训练营第55天｜最小生成树：prim、kruskal算法

最小生成树

卡码网 53. 寻宝

prim算法

代码随想录 prim算法精讲

有一个大坑，自己建立邻接矩阵的时候一定记得要双向。

import heapqV, E = map(int, input().split())graph = [[-1]* (V+1) for _ in range(V + 1) ]for _ in range(E):s,t,val = map(int, input().split())graph[s][t] = val# 确保是一个无向图graph[t][s] = valvisited = [False] * (V + 1)res = 0
min_heap = []
# 建立一个小顶堆？def add_edges(i):visited[i] = Truefor j in range(0, V + 1):if visited[j] == False and graph[i][j] != -1:heapq.heappush(min_heap, (graph[i][j], i, j))add_edges(1)while min_heap:weight, s, t = heapq.heappop(min_heap)if not visited[t]:res += weightadd_edges(t)print(res)

kruskal算法

代码随想录 kruskal算法精讲

class UnionFind:def __init__(self, size):self.parent = list(range(size+1))def find(self, node):if self.parent[node] != node:self.parent[node] = self.find(self.parent[node])return self.parent[node]def union(self, s, t):parent_s = self.find(s)parent_t = self.find(t)if parent_s != parent_t:self.parent[parent_t] = parent_sdef is_same(self, s, t):return self.find(s) == self.find(t)def kruskal(V, edges):edges.sort(key=lambda x: x[2])uf = UnionFind(V)res = 0for s,t,weight in edges:if uf.find(s) != uf.find(t):uf.union(s, t)res += weightreturn res
V, E = map(int, input().split())data = []
for _ in range(E):data.append(list(map(int, input().split())))res = kruskal(V, data)print(res)