代码随想录算法训练营第六十天| 图论7—卡码网53. 寻宝
图论第七天，prim和kruskal算法，说实话都没看的很懂，有点抽象难理解，只能照着题解理解一下了。
53. 寻宝（prim）
53. 寻宝（第七期模拟笔试）
复制一下网站上的prim算法的结论
prim算法三部曲
- 第一步，选距离生成树最近节点
- 第二步，最近节点加入生成树
- 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
minDist数组是prim算法的灵魂，它帮助prim算法完成最重要的一步，就是如何找到距离最小生成树最近的点。再来帮大家回顾minDist数组的含义：记录每一个节点距离最小生成树的最近距离。我们根据minDist数组，选取距离生成树最近的节点加入生成树，那么minDist数组里记录的其实也是最小生成树的边的权值。
节点数v和边数e，不可达的点对初始化为10001。读取边信息，更新邻接矩阵，表示每对相连节点之间的权重。定义两个辅助数组，visited用于标记哪些节点已加入最小生成树，minDist用于记录每个节点到当前生成树的最短距离。主循环执行v次，每次选出未加入树的、距离当前生成树最近的节点，并更新其他节点的minDist值。最后，累加这些最短边的权重得到最小生成树的权重值并输出。
# 接收输入
v, e = list(map(int, input().strip().split()))
# 按照常规的邻接矩阵存储图信息，不可达的初始化为10001
graph = [[10001] * (v+1) for _ in range(v+1)]
for _ in range(e):x, y, w = list(map(int, input().strip().split()))graph[x][y] = wgraph[y][x] = w# 定义加入生成树的标记数组和未加入生成树的最近距离
visited = [False] * (v + 1)
minDist = [10001] * (v + 1)# 循环 n - 1 次，建立 n - 1 条边
# 从节点视角来看：每次选中一个节点加入树，更新剩余的节点到树的最短距离，
# 这一步其实蕴含了确定下一条选取的边，计入总路程 ans 的计算
for _ in range(1, v + 1):min_val = 10002cur = -1for j in range(1, v + 1):if visited[j] == False and minDist[j] < min_val:cur = jmin_val = minDist[j]visited[cur] = Truefor j in range(1, v + 1):if visited[j] == False and minDist[j] > graph[cur][j]:minDist[j] = graph[cur][j]ans = 0
for i in range(2, v + 1):ans += minDist[i]
print(ans)53. 寻宝（kruskal）
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
kruscal的思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
不同的点是在重点维护边，所以定义边的类edge存储每条边的两个端点和权重，初始化father并查集数组判断是不是环。节点数v和边数e与prim算法中是一样的，并将所有边读入一个列表中。随后进入Kruskal 函数，先按边权从小到大排序，然后遍历所有边，检查该边的两个端点是否已属于同一个集合，若不在同一集合中则将其合并并将该边的权重加入最终结果中。这个过程直到所有节点连通为止。
class Edge:def __init__(self, l, r, val):self.l = lself.r = rself.val = valn = 10001
father = list(range(n))def init():global fatherfather = list(range(n))def find(u):if u != father[u]:father[u] = find(father[u])return father[u]def join(u, v):u = find(u)v = find(v)if u != v:father[v] = udef kruskal(v, edges):edges.sort(key=lambda edge: edge.val)init()result_val = 0for edge in edges:x = find(edge.l)y = find(edge.r)if x != y:result_val += edge.valjoin(x, y)return result_valif __name__ == "__main__":import sysinput = sys.stdin.readdata = input().split()v = int(data[0])e = int(data[1])edges = []index = 2for _ in range(e):v1 = int(data[index])v2 = int(data[index + 1])val = int(data[index + 2])edges.append(Edge(v1, v2, val))index += 3result_val = kruskal(v, edges)print(result_val)