代码随想录冲冲冲 Day55 图论Part7

53. 寻宝（第七期模拟笔试）

这道题讲的是如何使用prime算法去计算一个图中连接所以点的最小距离

就以这道题为例子

首先要记录各个边的权重 由于是无向图所以两个方向都要记

之后需要有一个数组去记录所有节点到最小生成树的最小距离 

还需要一个vector去记录每个节点是否在中

如果想把7个节点连接起来 最多只需要 n - 1 6个节点就可以了 这里就是选了1 - 6这六个

然后开始三部曲

1.选择一个距离生成树最小的节点 在选节点的时候要考虑两点： 不能在树中 而且距离要更近

所以需要一直去更新

2.选择好后加入树中

3.根据加入完之后的情况，更新其他节点与最小生成树的距离

但是由于能够变化的只有刚刚加入的这个节点

所以只要更新这些临边的mindist就行了

拓展： 如果说要打印出具体的路径

那么需要添加一个parent数组，用来记录点之间的相连关系

在后续更新值的时候 让非树中节点指向树中节点 这个时候跟新的原因是 

我们根据 minDist数组，选组距离 生成树 最近的节点 加入生成树，那么 minDist数组里记录的其实也是 最小生成树的边的权值。

既然 minDist数组 记录了 最小生成树的边，是不是就是在更新 minDist数组 的时候，去更新parent数组来记录一下对应的边

简单点理解的话就是在这一步会筛选出离这个刚刚加入的节点最近的节点 用parent来把最近节点指向刚刚加入的节点，这个过程中会把所有和刚刚加入树的节点都先连上，后面如果有更近的会更新

我们这里就不用在意方向，代码中 为什么 只能 parent[j] = cur 而不能 parent[cur] = j 这么写呢？

如果写成 parent[cur] = j，在 for 循环中，有多个 j 满足要求， 那么 parent[cur] 就会被反复覆盖，因为 cur 是一个固定值。

举个例子，cur = 1， 在 for循环中，可能 就 j = 2， j = 3，j =4 都符合条件，那么本来应该记录 节点1 与 节点 2、节点3、节点4相连的。

如果 parent[cur] = j 这么写，最后更新的逻辑是 parent[1] = 2, parent[1] = 3， parent[1] = 4， 最后只能记录 节点1 与节点 4 相连，其他相连情况都被覆盖了。

如果这么写 parent[j] = cur， 那就是 parent[2] = 1, parent[3] = 1， parent[4] = 1 ，这样 才能完整表示出 节点1 与 其他节点都是链接的，才没有被覆盖

+++++++++++++++++++++++++++++++++++++++++++++++++++++

第二部分 如何使用kruskal方法解决这个问题

卡码网KamaCoder

kruskal这个方法是记录边的方法

首先把所有的边按照权重大小排序

设置后 并查集 具体方法是 遍历一条边 看这条边的两个端点

如果两个端点root不同 就加入一个集合 也就是一个root中

同时累加这个边的值

如果是同一个root 说明要成环了 那么就不累加值 也不join进root中

拓展1：

如果要是要把边生成出来 只要在收结果这里吧边记录下来就行了

最后总结一下什么时候用prime什么时候用kruskal

一句话来说 如果说 一个图中 点少 那么就prime

如果说边少 那就kruskal