1 00:00:00,000 --> 00:00:07,790 大家好,数据结构与算法,这一讲介绍第七章图的最小生成树 2 00:00:07,790 --> 00:00:14,345 最小生成树是图的一个子图,那 3 00:00:14,345 --> 00:00:20,900 这个子图是一个树结构,也就是N个点正好有N-1条边 4 00:00:20,900 --> 00:00:27,130 把这些图的节点关联起来,而且这个最小生成树 5 00:00:27,130 --> 00:00:33,360 它的这些相应的边的权值总和是最小的 6 00:00:33,360 --> 00:00:37,550 那我们首先介绍一个Prim 7 00:00:37,550 --> 00:00:44,040 算法,这个算法跟我们单元最短路的Dijkstra算法是类似的 8 00:00:44,040 --> 00:00:53,360 首先,从图里面任何一个顶点出发,把这个顶点包含到最小生成树MST里面 9 00:00:53,360 --> 00:00:58,220 然后,我们把这个图的节点呢 10 00:00:58,220 --> 00:01:03,080 分成两个集合,就是已标记集和未标记集 11 00:01:03,080 --> 00:01:07,245 那我们的已标记集合,未标记 12 00:01:07,245 --> 00:01:15,080 集之间,它们的顶点关联的这些边我们取这个权值最小的那个边 13 00:01:15,080 --> 00:01:19,670 把这个边呢,就加入到, 14 00:01:19,670 --> 00:01:24,260 我们的最小生成树,当然,它相应的那个点也带过 15 00:01:24,260 --> 00:01:29,795 来,然后,带过这个新点以后呢,这个未标记集 16 00:01:29,795 --> 00:01:35,330 跟已标记集的那样一个距离,可能就发生了相应的改变 17 00:01:35,330 --> 00:01:40,850 那,我们还是在这样的,啊, 18 00:01:40,850 --> 00:01:46,580 在这样的这些关联这个已标记集和未标记集的,这样的 19 00:01:46,580 --> 00:01:52,310 这些边里面呢,找最小的那一个,我们不断的贪心的进行这个 20 00:01:52,310 --> 00:01:57,690 方法,那直到所有的这些点都 21 00:01:57,690 --> 00:02:03,070 进到了这个最小生成树里边,而且呢,正好有N-1条边 22 00:02:03,070 --> 00:02:10,790 那我们,来证明一下Prim算法它的最小生成树 23 00:02:10,790 --> 00:02:17,010 性质,这其实是Prim这个贪心法它的一个贪心性质 24 00:02:17,010 --> 00:02:22,450 对于我们这么一个Prim 25 00:02:22,450 --> 00:02:27,420 算法,假设T是一棵正在构造的 26 00:02:27,420 --> 00:02:35,320 树,它相应的有这个未标记的这些没有处理的节点和 27 00:02:35,320 --> 00:02:41,170 边,假设有一个边, 28 00:02:41,170 --> 00:02:47,910 它是关联这个已标记和未标记的这部分 29 00:02:47,910 --> 00:02:52,015 的这个边E,那这个边呢,它是所有的 30 00:02:52,015 --> 00:02:56,120 这些关联这俩个集合的这些边里面呢 31 00:02:56,120 --> 00:03:02,630 最小的权值那一个,那我们可以 32 00:03:02,630 --> 00:03:08,180 说呢,一定存在G的某一棵这个MST 33 00:03:08,180 --> 00:03:12,205 那这个MST呢,它首先当然是包含 34 00:03:12,205 --> 00:03:16,230 了T,这个T是一个正在生成的局部的一个树 35 00:03:16,230 --> 00:03:22,940 那而且呢,它一定能够包含这个E, 36 00:03:22,940 --> 00:03:27,050 这一条边,那我们用反证法来证一下 37 00:03:27,050 --> 00:03:31,160 那首先呢,我们假设 38 00:03:31,160 --> 00:03:38,770 这个G的任何一棵包含T的MST都不包含E, 39 00:03:38,770 --> 00:03:45,240 那,假设这样的一棵树呢,假设我们找到了,叫做T' 40 00:03:45,240 --> 00:03:47,940 那因为T' 41 00:03:47,940 --> 00:03:53,460 是连通的,因此,它必然有某一节点属于 42 00:03:53,460 --> 00:03:58,620 这个已标记的这样的部分,就是 43 00:03:58,620 --> 00:04:03,780 设为Vp,然后呢,另外一个节点呢Vq,属于这个未标记 44 00:04:03,780 --> 00:04:08,625 的部分,那这个Vp和Vq连的这样一条边 45 00:04:08,625 --> 00:04:13,470 E’呢,就把这个已标记和未标记的部分给关联起来 46 00:04:13,470 --> 00:04:20,525 因为T'是连通的,所以我们必须要找到这么一个,当然了在 47 00:04:20,525 --> 00:04:27,580 这个已标记集合里面呢,Vx到Vp有一条路径,在未标记的点里面,Vy和Vq 48 00:04:27,580 --> 00:04:33,100 有一条路径,那我们把, 49 00:04:33,100 --> 00:04:38,670 E加入到T'里面,然后我们删掉 50 00:04:38,670 --> 00:04:45,780 那个E',那我们就得到了一个新的树假设 51 00:04:45,780 --> 00:04:51,900 叫做T",那这个T“,它的权重 52 00:04:51,900 --> 00:04:56,490 一定不会超过刚才的那个T',因为它们的区别 53 00:04:56,490 --> 00:05:00,450 就是,只是有一个呢,是 54 00:05:00,450 --> 00:05:07,090 用了E替换了这个E',而我们知道,在所有这样的边里面呢,E 55 00:05:07,090 --> 00:05:13,730 是权值最小的,显然,T"的这个权值和呢,是不会大于T' 56 00:05:13,730 --> 00:05:20,410 的,那因此呢,我们就证明了,T” 57 00:05:20,410 --> 00:05:24,800 是一棵包含了E的这么一个最小 58 00:05:24,800 --> 00:05:30,050 生成树,那因此呢,就跟我们前面的假设是矛盾的, 59 00:05:30,050 --> 00:05:34,915 那就证明了,我们的结论是正确的,也就 60 00:05:34,915 --> 00:05:39,780 是说Prim算法呢,它是具有MST这样一个 61 00:05:39,780 --> 00:05:46,290 贪心性质的,那也就是说明了Prim算法,它在构造最小生成树的过程 62 00:05:46,290 --> 00:05:54,180 中,每一次,都找这个已标记集和未标记集里面沟通它们两个这个桥梁边里面 63 00:05:54,180 --> 00:06:01,160 的,具有最小权值的边是正确的,最后能够得到一个整体最优的最小生成树 64 00:06:01,160 --> 00:06:05,330 那我们看一下,Prim算法,它的一个构造过程 65 00:06:05,330 --> 00:06:09,845 那,首先呢,我们初始化这个 66 00:06:09,845 --> 00:06:14,360 Mark数组,让它呢,就是标记每一个节点都是没有被访问的 67 00:06:14,360 --> 00:06:22,260 还有一个dist,这样一个最小距离的这样一个数组,那我们让它呢, 68 00:06:22,260 --> 00:06:29,800 它的距离值都是正无穷,而且呢,它的前驱都是这样的一个选定的 69 00:06:29,800 --> 00:06:34,115 起始点S,那我们把这个起始点,它 70 00:06:34,115 --> 00:06:38,430 的距离呢,是设为0,因为它自己到自己是0距离的, 71 00:06:38,430 --> 00:06:45,170 然后把它标记为,已经访问,然后,我们从S开始进行处理, 72 00:06:45,170 --> 00:06:50,950 那因为我们这样一个最小生成树,它是 73 00:06:50,950 --> 00:06:56,730 有N个点,N-1条边的,刚才我已经把这个起始点加 74 00:06:56,730 --> 00:07:04,360 入了,所以,我还需要加入N-1个点,因此,是这里循环N-1次 75 00:07:04,360 --> 00:07:12,395 那我们首先呢, 就是来判断,这个 76 00:07:12,395 --> 00:07:17,730 因为,我们前面这个V,那我第一个V呢,就是赋的这个S 77 00:07:17,730 --> 00:07:23,040 起始点啊,那,因为这个V的加入,那,我们可能需要 78 00:07:23,040 --> 00:07:28,350 刷新跟V相邻的那些点的D值,那我就 79 00:07:28,350 --> 00:07:32,690 看这个V加入以后, 80 00:07:32,690 --> 00:07:37,030 那这个V到邻接点的形成的这个边 81 00:07:37,030 --> 00:07:42,290 它的权值是不是小于原来邻接点 82 00:07:42,290 --> 00:07:47,550 存的那个到已处理点那个点集的距离值,如果小 83 00:07:47,550 --> 00:07:54,580 那我就用这个更小的,来替换,而且,这个,Prev呢,就记为V,是V来引入 84 00:07:54,580 --> 00:07:58,740 这个的,然后呢,我们在这个 85 00:07:58,740 --> 00:08:04,720 D数组里面找最小值,那我们标记为V这个 86 00:08:04,720 --> 00:08:12,160 点,那这个V这个点,它假设是具有最小的dist 87 00:08:12,160 --> 00:08:19,600 那根据我们这个函数的返回呢,如果这个V是等于-1的,也就是说,表示不存在这样的点 88 00:08:19,600 --> 00:08:25,610 那我就,整个要返回,尽管我们这里还没有找到N-1 89 00:08:25,610 --> 00:08:31,620 个这个除了原意外的其他的点,但是,我已经找不到这样的 90 00:08:31,620 --> 00:08:36,540 一个连通的,这么一个最小支持树了,所以我返回 91 00:08:36,540 --> 00:08:44,510 报错,如果是找到了一个合适的具有最小的dist值的那个 92 00:08:44,510 --> 00:08:50,360 点,那我们就把这个点标记为已经访问 93 00:08:50,360 --> 00:08:55,870 了,而且呢,把这个点和相应的边呢,加 94 00:08:55,870 --> 00:09:01,380 入到我们的最小生成树里面,然后再进入下一次循环,再继续 95 00:09:01,380 --> 00:09:06,185 找那在dist数组里面找最小,我们这么一个函数, 96 00:09:06,185 --> 00:09:10,990 是这么设定的,首先呢,我初始的这个V呢, 97 00:09:10,990 --> 00:09:15,810 是等于-1,那初始的这个最小的距离呢,是 98 00:09:15,810 --> 00:09:20,630 正无穷,那我们来对整个这个dist数组来 99 00:09:20,630 --> 00:09:26,740 扫描,如果是这个相应的这个顶点没有 100 00:09:26,740 --> 00:09:32,850 被访问,而且它的dist值呢,小于我们当前记录的 101 00:09:32,850 --> 00:09:36,940 这个MinDdist,那我就把这个V呢,修改为记录的这个MinDdist 102 00:09:36,940 --> 00:09:41,030 那我就把这个V呢,修改为我现在看到的这个i,而且它的dist呢,也做相应的修改 103 00:09:41,030 --> 00:09:46,020 那最后,我们完成这一层循环,就找到了这里面没有 104 00:09:46,020 --> 00:09:51,010 访问的具有最小dist值的那个顶点V,或者是说,如果 105 00:09:51,010 --> 00:09:58,560 找完以后,没有这样的值,那就是V=-1,也就是说,它这个图,可能是不连通的, 106 00:09:58,560 --> 00:10:05,380 情况,那Prim算法,它的时间复杂度的分析,跟Dijkstra算法是非常 107 00:10:05,380 --> 00:10:12,200 类似的,首先,它的算法框架就跟这个单元最短路的框架是相同的, 108 00:10:12,200 --> 00:10:17,210 而它这里面的,距离值呢,它不需要累计,它更简单 109 00:10:17,210 --> 00:10:22,220 那,我在刚才介绍的这个算法里面,我们比较dist数组里面的 110 00:10:22,220 --> 00:10:26,740 这些元素的时候呢我们要确定代价最小的 111 00:10:26,740 --> 00:10:34,060 那个边,总的来说是需要O(N^2)的时间,因为我们每次都是对整个dist数组扫一遍 112 00:10:34,060 --> 00:10:40,160 而且,我要扫N次,那这种算法呢,它 113 00:10:40,160 --> 00:10:46,260 适合于密集图,那对于稀疏图呢,我们可以像前面介绍的Dijkstra算法那样 114 00:10:46,260 --> 00:10:50,090 用最小堆来保存这个最短的距离, 115 00:10:50,090 --> 00:10:54,370 那我们再来介绍一个,Kruskal 116 00:10:54,370 --> 00:11:00,200 算法,那前面的Prim算法呢,它实际上是从这个顶点出发 117 00:11:00,200 --> 00:11:04,855 然后,一个一个的拉它的相邻的那个点 118 00:11:04,855 --> 00:11:09,510 那Kruskal算法,它可以看做是从边 119 00:11:09,510 --> 00:11:17,580 出发,那首先,顶点它根本不需要考虑了,所有的点都已经应该是包括在我们这个最小生成 120 00:11:17,580 --> 00:11:23,810 树里面,那我们就来看边,那先把这个具有最小权重的边 121 00:11:23,810 --> 00:11:28,495 给它拉进来,然后呢,再去考虑下一个,具有次 122 00:11:28,495 --> 00:11:33,180 小权重的边,然后,我们不断的去来引入这些边 123 00:11:33,180 --> 00:11:40,585 在引入的过程中呢,特别要注意就是看一下,边所关联的这两个 124 00:11:40,585 --> 00:11:47,990 点,它们是不是已经在一个连通分量里面,如果已经在一个 125 00:11:47,990 --> 00:11:54,950 连通分量里面,你还把它关联起来,那就会形成环,所以对这样的边呢,我们要 126 00:11:54,950 --> 00:12:00,395 给它去掉,一直到我们找到了N-1个合适 127 00:12:00,395 --> 00:12:05,840 的边为止,把整个这N个点呢,就连成了一个最小 128 00:12:05,840 --> 00:12:12,790 支撑树,那我们看这个算法的这么一个示意,那首先呢,我就设定 129 00:12:12,790 --> 00:12:17,985 这7个点,它都是独立的连通分量, 130 00:12:17,985 --> 00:12:23,180 然后,我找这个权值最小的边,那我就把这两个连通分量给连起来 131 00:12:23,180 --> 00:12:30,225 然后呢,我们一直这么找,那当找到V3V6这个边的时候 132 00:12:30,225 --> 00:12:34,470 我们发现,V3V6它本来就在一个连通分量 133 00:12:34,470 --> 00:12:42,420 里面,那如果你还加一条边,那就会使得它形成一个环,所以这个边,我们要 134 00:12:42,420 --> 00:12:47,520 抛弃,然后我们继续找,一直找N-1个这样的边, 135 00:12:47,520 --> 00:12:52,400 为止,那看一下Kruskal最小生成树的 136 00:12:52,400 --> 00:12:57,820 算法,那首先,我们把所有的这些, 137 00:12:57,820 --> 00:13:01,885 有效的边给它放到一个最小堆里面去, 138 00:13:01,885 --> 00:13:05,950 那在最小堆里面,我们就非常方便找那个 139 00:13:05,950 --> 00:13:13,800 最小值了,然后,我们设立呢,那样一个等价类的个数,这么一个变量,那这个变量 140 00:13:13,800 --> 00:13:17,520 最开始的时候,就等于整个图里面的节点的个数, 141 00:13:17,520 --> 00:13:22,180 然后呢,我们当这个 142 00:13:22,180 --> 00:13:26,840 等价类的个数是大于1的时候, 143 00:13:26,840 --> 00:13:32,465 也就是说,你这些等价类还没有合在一起,成为一个树结构,它是 144 00:13:32,465 --> 00:13:41,480 连通的,那我们在这种情况下呢,我就要不断的去把它们合在一起,合在一起,然后最后成为 145 00:13:41,480 --> 00:13:48,410 一个树,那我们首先呢,来判断这个堆是不是空的,如果 146 00:13:48,410 --> 00:13:52,790 空,而且呢,你现在这个等价类 147 00:13:52,790 --> 00:13:57,170 的个数呢,还大于1,那就表示这个图是不连通的,我没办法处理了, 148 00:13:57,170 --> 00:14:03,440 那就返回,说我找不到这样的MST,否则呢, 149 00:14:03,440 --> 00:14:11,810 就是不空的情况下,当然,我们就可以从堆里面找出一个合理的具有权值当前最小的 150 00:14:11,810 --> 00:14:16,545 那个边,那我们看一下这个边,关联到的两个顶点 151 00:14:16,545 --> 00:14:21,280 这两个顶点,看一下,它们是在不在同一个等价类里 152 00:14:21,280 --> 00:14:29,980 面,如果,它们不在同一个等价类里面呢,我们就可以把它合并,就引入 153 00:14:29,980 --> 00:14:35,180 这一条边,那就是说,这个边呢,可以加入到这个最小生成树里面 154 00:14:35,180 --> 00:14:39,540 那它们关联的顶点,早就已经是加入了,因为 155 00:14:39,540 --> 00:14:46,220 我们说,Kruskal算法,它一开始就把所有的点都加到这个最小生成树里面,它只是逐步 156 00:14:46,220 --> 00:14:52,900 来加边,要加N-1条边,那这个等价类的个数呢,显然 157 00:14:52,900 --> 00:14:57,770 就减1了,那我们再不断的循环,一直到这个等价, 158 00:14:57,770 --> 00:15:02,640 类的个数等于1,那我们就成功的找到了这么一个最小 159 00:15:02,640 --> 00:15:07,440 生成树,那我们看一下这个算法的演示过程 160 00:15:07,440 --> 00:15:12,240 那首先我们对这些边呢,都是进行了排序,我把它插到了堆里面, 161 00:15:12,240 --> 00:15:16,700 然后,我们逐个的去找这个最小的 162 00:15:16,700 --> 00:15:22,910 这个边,那找这个最小边呢,我们就不断的去合并这样 163 00:15:22,910 --> 00:15:28,410 的等价类,那我们看,合并到这个BC的时候, 164 00:15:28,410 --> 00:15:36,570 那我来考虑,因为BC它在同一个等价类里面,我们不能够合并它,那你看这个, 165 00:15:36,570 --> 00:15:41,070 图呢,如果是,把这个BC这个边引入的话, 166 00:15:41,070 --> 00:15:45,540 就ABC会形成环,它不是一个最小 167 00:15:45,540 --> 00:15:50,010 生成树,所以呢,这条边,我们就放弃,我继续取其他的边 168 00:15:50,010 --> 00:15:57,250 那最后呢,我们这个算法就是形成了这7个节点 169 00:15:57,250 --> 00:16:04,720 ,6条边,这是6条红色的边,所形成的一个最小 170 00:16:04,720 --> 00:16:07,660 生成树, 171 00:16:07,660 --> 00:16:13,670 那,Kruskal算法,它是应用了这样的一个 172 00:16:13,670 --> 00:16:20,830 并查集,来合并等价类的,那我们 173 00:16:20,830 --> 00:16:27,560 在这个Kruskal算法的一个处理过程中,其实我们每次都是处理那个 174 00:16:27,560 --> 00:16:34,420 最小边,那最坏的情况下呢,可能是这个所有的边都在堆里面,每次取 175 00:16:34,420 --> 00:16:41,280 最小,每次取最小,就是一个堆排序的时间,那这个算法呢,就跟边的个数是有关系的 176 00:16:41,280 --> 00:16:47,670 是e * log e的时间,那在很多情况下,其实我们只 177 00:16:47,670 --> 00:16:51,500 需要略多于N次这样的查找, 178 00:16:51,500 --> 00:16:56,500 最小,就可以完成了对整个这个 179 00:16:56,500 --> 00:17:05,070 最小生成树的一个N-1条边的查找的工作,所以,其实它的时间接近于N*log e 180 00:17:05,070 --> 00:17:11,260 那我们最后给几个思考题,首先呢,最小生成树,它是不是唯一的 181 00:17:11,260 --> 00:17:15,460 可以想一下,它显然不是唯一的 182 00:17:15,460 --> 00:17:22,240 那我们如果对于不唯一的这个情况呢,我们应该怎么样设计这个算法 183 00:17:22,240 --> 00:17:29,150 来生成所有的最小生成树。另外呢,我们再思考一下,如果这个边 184 00:17:29,150 --> 00:17:36,690 的权值都不相同的情况下,那是不是唯一的呢?这个答案,显然一定是 185 00:17:36,690 --> 00:17:42,130 唯一的,谢谢大家