2022.4.4

WEEK11.2 最小生成树

一、内容

1.生成树（Spanning Tree）

前提一个图是无向图，由这个图生成的一个包含所有节点的树就是生成树。
一个图可以生成很多树，其中权重最小的生成树就为最小生成树（MST）

最小生成树样例 这两个都是生成树，我们并不在意生成树是否繁茂 看看这几个图，那个是生成树？

答案是最下面那一个

2.最小生成树和最短路径树的差别

一个图的最小生成树只有一个，而对于不同节点开始的最短路径会有所不同
它们两个是有可能相同的

3.切分定理（The Cut Property）

最小生成树可以在这个定理下完成

有如上的图，我们把节点切分成了两个集合，其连接两个集合的边称为横向边（如图红色边所示）

有重要结论：对任意切分，所有横向边（Crossing Edge）的最短一条边一定是最小生成树中的一条边
注意这个切分不一定是我们看到的切分，我们只要能把节点分成两个集合就行

可以用反证法证明，假设不是最小生成树的边，那么就会生成环，矛盾

4.Prim 算法（概念版）

我们来讲一个利用切分来形成最小生成树的一个算法——Prim算法

首先，我们以任意一个节点为起点（最小生成树不用考虑节点，但方便起见，我们还是来一个起点） 并且有一个记录边的数组 然后从起点（这里为0）的邻接节点中权重最小的节点加入生成树 “加入”的表现形式就是更新edgeTo数组 然后，继续找邻接节点权重最小的那个（注意，我们仍需考虑0的节点） 此时，有相同的情况，我们任意选一条就行（只选一条！） 以此类推，我们得到一个最小生成树 数组结果

可见，Prim算法就是在已加入MST的节点的邻接边中，找到一条最小的边，然后将其和节点加入到MST

5.效率分析及其改善

我们刚刚讲的Prim算法，总是需要遍历一下邻接边找到最小边，或许我们可以优化一下？

我们用了一个优先队列，存放其节点到开始起点的距离 同时也有了一个距离数组

随后，我们不断deque（出队）优先队列，同时松弛所出队的节点所在的临界边的权重

例如一开始出队0，于是我们看其邻接边的权重 更新 更新

我们之前讲的一次只加入一条边，现在一次加入两条边，但不要认为我们已经认定了这两条边就是最终的边，当我们之后出队队列中的元素时，我们才能确认

出队了2节点 此时2被加入到了MST

结果就是，每次出队一个节点，就确定了MST中的一条边
但和概念版Prim算法不同的是，我们找下一条边时，我们只需找邻接2的三条边，而不用看邻接0的边（虽然在步骤上，如果距离小的话，我们需要更新邻接2的三条边的距离）

更新，注意这里1的距离是2，因为5大于2 更新

注意这里的权重和Dijkstra的距离有所不同，后者是到开始起点的距离，而这里是到邻接节点的距离

于是4出队，并更新数组 然后，继续对4的邻接边进行更新 更新队列 更新数组

这里注意一下，虽然没有显示，但是是有marked数组的来标记访问的

同理1出队，并更新

然后循例进行，直到优先队列为空结束为止

6.和Dijkstra比较

基于优先队列的Prim和Dijkstra算法很像，后者是根据到开始起点的距离来出队的，前者根据出队节点的距离来更新

代码实现 代码实现

7.Kruskal 算法

这也是一个最小生成树的算法，这个比Prim简单（老师说的）

首先，我们先把每条边按升序排序

排序 从最小的开始，只要加入的边不形成环，就加入 此时到了这条边 发现形成了环，不加入MST 最后找到一条边，使得MST无环且加入的边数为V - 1

当然，我们也可以用优先队列来优化算法

同样，按权重加入优先队列 同时，还有两个数组维护，两个数组都加入边，WQU检查有无环，MST是最终结果 首先出队最小的，然后检查是否有环 继续出队，检查 此时的数组 同理，出队，维护数组 继续 继续 当加入1-4边时，发现WQU数组1和4是连接的，说明有环，不加入 继续出队，直到MST有V-1条边，结束

可见，Kruskal算法每次考虑的边都是最小边

Prim和Kruskal

Prim是从1个节点开始发展MST，而Kruskal每次从最小边（不成环）开始加入，直到生成MST

伪代码

时间消耗为O（ElogV）

小结

结语

从几个星期前开始，就开始学习cs61b 2018sp，我处于对自身基础的考量，开始以博客的方式学习，现在终于到一段落了。
虽然还有几节课，我决定在这里结束，当然剩下学习的数据结构我会以专题的形式补上，尽情期待！
我本以为我有很多话想说，但真到了这个时候，还是感慨为多吧。其中还是有很大的遗憾的，比如作业中一些库我没找到，以至于丧失了有趣的编程体验（真的很有趣）。这一趟课程学习下来，我的java基础扎实了，对于数据结构的理解更深了，对于编程不再那么畏首畏尾了。感谢josh hug老师的教授以及伯克利的课程分享，我切实感受到名校的学习氛围。
从今以后，我会更加努力地学习，加油！