00:00
同学们,我们继续来学习下一个算法。那讲完普里姆算法过后呢?我们再来看另外一种可以求最小生成数的算法叫。克鲁斯卡尔算法。那在前面我们讲过,大家还记不记得我们在前面讲这个。普里姆算法的时候,我们说过求最小生成数呢,目前比较经典的两个算法是普里姆算法和。克鲁斯卡尔算法。我们已经把普里姆算法给各位同学讲了,那我们来看看克鲁斯卡尔算法,那从这地方我们可以看出来,克鲁斯卡尔算法呢,仍然是求最小生成数的,对不对?这点大家要有一个基本的认识,那么下面呢,我们仍然以一个应用场景引出。克鲁斯卡尔算法。同学们可以看到这儿呢,有一个公交站问题,同学们看这里有一张图,OK,这张图一共有。
01:05
ABCDEFG,一共七个点,那我们可以设这样一个话题,就是说在某一个城市需要新增七个站点。七个站点,那分别是ABCDEFG,现在我们需要把这七个站点呢,联通,联通它的要求是这样子的,他已经告诉你。站点之间用边的全来表示,你比如说A和BA和B这两个站点呢,它的距离是12个公里。OK,注意啊,A和B现在还没有修路,就说他告诉你A和B这两个地它的距离是12,但是你修不修这条路呢,要取决于你算法的结果。明白,他的要求就是这样子的,问如何修路,保证各个站点都能够连通,并且总的修建公里。
02:02
的这个里程数是最短的。其实大家有没有发现,像这种所谓的公交站问题,跟我们前面讲的修道路问题其实是一样的,完全是一样的,只是换了另外一种说法,对不对?你以前是修路,现在是公交站,其实都完全一样。好,这是我们克鲁斯卡尔算法的一个应用场景,那么下面呢,我们就给同学们来看看何为克鲁斯卡尔算法。首先我们对克鲁斯卡尔算法做一个基本的介绍。克鲁斯盖算法对应的英文是car。那么它是用来求加权连通图的最小生成数算法,这点在前面已然给同学们介绍过了。它的基本思想是这样子的,首先第一步按照全值从小到大顺序选择N减一条边,为什么是N减一条边呢?因为你有N个站点。
03:02
你有N个点,其实我们需要N减一条边就可以把它连通,你比如说你有A和B这两个站,那么你其实一条边就可以把它们连接起来,如果你要再来一个C,其实这个C呢,你随便。连,比如说你A和C点,那么这三个点也就连起来了,你B和C连也可以,因此我们说N个顶点,其实只需要N减一条边。就能够构成这种这种这个什么呢?就是联通联通好,具体的做法是怎么样子呢?首先构构造一个只含N个顶点的森林,然后依照全从小到大从连通网中选择边加入到森林中。并且使森林不要产生回路,直到森林变成一棵树为止。同学们。这个地方有。有提炼出两句话,大家有没有发现克鲁斯卡尔算法的核心是两,我们可以看到其实是两点,第一点呢,就是要对我们这个边的全子进行排序。
04:13
是不是首先要排序啊,就是要对我们N这个全值边的全值进行一个排序,第二点是什么的,同学们看到它把这个从小到大的这个边呢,加入到森林,同时还要判断有没有产生回路,就是说不停的加加入。对不对?加入的同时呢,要判断是否产生回路,问题来了,我们前面呢,没有讲过回路的概念,是不是同学们我们没有讲过回路的概念,那么究竟是什么回路呢?待会儿我们讲。啊,就会说这个事儿,同学们克鲁斯卡尔的一个算法,如果我们按照这个思路来讲。同学们,大大部分同学应该是比较抽象和模糊的,就说不知道他到底是怎么做的对不对。
05:03
那没有关系,我们仍然图解一下克鲁斯卡尔算法,同学们看我这里呢有一张。有一张图来说明克鲁斯卡尔怎么解决刚才的这一个公交站问题的思路,那我们把这个图呢给各位同学打开看一眼。这个一看就一目了然。同学们,我们把。这一个图解打开,我们搂一搂,首先看。他说现在呢?在含N,在含有N个顶点的连通中,选N减一条边,构成一棵极小连通子图,也就是我们所说的最小生成树。那么这个时候,那这写的啊,最小参数,那么我们应该选哪些边呢?同学们看我的思路就来了,首先同学们看到这张图。这张图呢,我尝试着画了三种连通方式,大家有没有发现不同的连接方式,它的全值总和是不一样的,你比如说如果我们按照这样连,是不是一共有六条边呢?因为你有七个顶点对应六条边嘛。
06:14
如果我们这样连通,它的总的边的全值加起来为43,而这样一种连通方式,大家有可以看到它的边的全值总和为36,要小一点的是不是好,我们还可以这样连,这样连也是一共六条边,也把它们连通了,那么它的全值总和为64,同学没有可以看到不同的连接方式,它的全值总和不一样。不一样。那么这就说明你在进行这个选择的时候,其实是多样化的。那么什么时候才是一棵最小生成树呢?就是全值最小的,就是你比如说假如我们这个36,我说的假如啊各位同学,假如我们这个这种连接方式,36是所有是所有连接方式里面最小的。
07:10
假如它是最小的,那么我们这种连接方式就是最优的,也就是我们待会儿克鲁斯卡尔能够推出的结果。因为它是最小的嘛。对,这就是我们要求的这一颗最小生成树,好,这是我们的一个目标。那么对于一个克鲁斯卡尔算法,它怎么样来?得到一个全值总和最小的生成数呢?它的思路是这样子的,OK,我们来看一下假设,注意听假设我们用数组R来保存最小生成数的结果,假如我们有个数组来保存最小生成数的结果,那么我的思路就来了,大家看第一步。我一点一点讲啊,各位同学认真听,首先呢,我们选取EF这条边。
08:02
为什么选这条边呢?因为这条边的全值是最小的,你们有没有发现二是所有边的全值最小的一条边,所以我们把它选出来。至于怎么选的,大家不用着急,待会有具体的代码实现,第二条边是不是三呢?诶,大家我们看C和D,它们是最第二小的这个边的两个顶点,所以说把C和D又选进去。那也就是在EF,我们要连C和D要连,那下一个呢,我们又把这一个D和E连起来,又选的D和E这条边,为什么选这条边,因为二三再下一个就是四是最小的了,依次排序嘛,从小到大进行选择,那再下一次就。有问题了,同学们看到,在下一次理论上,我们应该选择C和E。为什么选C和E?因为C和E它实际上是什么样?是在下一个较小的边。
09:07
那个全是小的边,所以应该选C和E,但是选择C和E呢,会形成回路。形成回路,因此这一条边我们是不会选择的,也就是这个时候,你会发现我们下次选的是B和F。你看B和F,其实你会发现它其实是大于五的,而且还大于六。那为什么我在第四步没有选择C和E,也没有选择C和F呢?就是因为这两种选择方式会构成回路。问题来了,同学们会在会想,诶,那怎么样才算是一条回路呢?不要着急,一会我会用一个图解的方式来给大家解释何为回路,一会就讲哈,我们先把这条线讲完,因为我一张嘴说不了两两条线的话,我先把这个讲完了,再给大家讲解回路的概念,怎么去判断,这肯定是个核心。
10:01
所以说下一步我们选择其实并不是C和E,也不是C和F,为什么呢?因为它会构成回路。为什么各种回路待会儿我们再说,而是选择了B和F7,于是第四步选择是BF这一条边。尽管它不是再下一个最小的,OK,再下面我们想E和G,一和G这条边是哪里呢?是这条边。好,这条边剪完了后呢,我们再选A和BA,和BA是这条边。那最后我们整个六条边的应该是如此这般的。123。是OK。这条边OK,这条边,也就是说我们整个六条边应该是老师现在标红的这六条边,他的全职总和是多少呢?应该是三加。四。加。加几呢?哦,二前面还有个二忘加了,对不对?二加三加四,下一个是加七,没有问题吧,下一个是加八,没有问题吧,下一个是A和B这条边是12。
11:12
那统共是多少呢?我们可以简单算一下,这是九,再加一个15。再加一个12 OK,那也就是说这边是24,再加12应该是等于36,也就是说如果待会儿我们克鲁斯卡尔算法能够得到这六条边,它的全值为36,就是最小的。这个就是它最小的。好,我们来看看刚才这一个说法的下一个文字描述,第一步选E和F,因为E和F最小,这是第一步。就是这样选的原因,好,第二步我不讲了,C和D是不是没有问题,大家看第三步D和F也没有什么可说的,那么第四一步B和F,第四一步本身上一步操作以后,你看我这写的很清楚,上一步操作以后,BC和E是最小的。
12:07
但是CE会构会和已经构成边构成回路。因此跳过。下一个呢,又应该选选什么?C和FC和F也要跳过,因为也会构成回路,所以说最后我们第四步选的是B和F,下面以此类推,我就不一个说了。那么呃,经过六步以后呢,我们最小生成数的边意思是这个我也不去念了,好吧,那现在现在我们来对克鲁斯卡尔算法做一个分析。同学们有没有发现?克鲁斯卡尔他的基本思想和做法其实是有两个问题要重点解决的。第一个,对图所有边按照全值从大到小。从小从小到大进行排序,那这个很简单,我们可以用任我们用前面我们学过的排序算法就可以搞定,比如说你用冒泡。
13:00
你有选择,你用插入都OK,都OK,所以第一个问题其实是比较容易解决的,第二个问题将边添加到最小生成数,如何判断已经构成了回路好。我们来看看第二个问题,因为第一个问题很好解决,我刚才讲了用排序算法就可以搞定第二个问题处理方法是这样子的,注意听记录顶点。在最小生成数的终点。顶点的终点是在最小生成数中与它连通的最大顶点,然后每次需要将一条边添加到最小生成数的时候,判断该边的两个顶点的中点是否重合,重合的话就构成回路。好了,同学们,第二个问题处理的方式,其实就是老师刚才说的这段话,但这段话说的呢?说实话,很多同学也可能不太明白老师在说什么,没有关系,我用一个图的方式再来讲解一下怎么样判断各种,也就是说用图的方式把我们问题二的处理方式的文字描述,用图解的方式给各位朋友讲解一下,其实也不也挺简单的了,来看一下我们来判断。
14:14
我们就以,我们就以在第四步的时候,为什么我们加的是B和F。为例进行讲解,来,各位同学注意听讲哈,将E和FC和DB和E,呃D和E加入最小生成之后,这几条边的顶点依次就是就有了终点了。那么什么呢?C的中点是F。为什么?因为这里面F它是最大的嘛,好的,从编号来说它是最大的是不是,因为你在加这个里面是不是ABCDEFG这样加的是不是,同学们好说F最大是不?C的中点是,C的中点是FD的中点也是f fe的中点也是FF的中点也是F,为什么它自己是自己的终点,因为它是最大的,所以说其实当我们这样做完了以后,同学们可以看到我们ABCDEF它们都有终点,而且都CF。
15:09
没问题吧,好,同学们看。那么。现在我们来看看终点的说明。刚才我其实就说,我刚才其实已经讲了,这些顶点的中点分别是F,那我为什么说是F呢?同学们可以看到它是这样子的。就是将所有顶点按照从小到大的顺序排好,某个顶点的终点就是与它连通的最大顶点。再听一遍,就是按照顶点从按照从小到大的顺序排好以后,某个顶点的终点就是与它连通的最大顶点,打个比方,CC的C的中点,C的中点为什么CF呢?因为C的中点从你把这几条边加进去过后,你C的与它连通的最大顶点其实就是F嘛。
16:02
是不是就是F,你们这个F它是最大的。它最大的一个顶点,所以说就是F,同样DEF就是这样的道理,所以说终点的概念其实大家就已经明白了,来我们看第二句话,因此接下来虽然C和ec和E这条边全是最小。是应该是C和一全最小,它应该是五了吧。C和ec和E本身是五,它是最小的,但是注意听,C和FC和E的中点现在已经是F了。你看这写的很清楚嘛,C和E的中点已是S,即它们中点相同,因此将C和E加这条边加入最小生存的话,就会构成回路。诶,因为你现在C和一的中点已经CF了,你你你在没有加这条边的时候,它就已经是有相同终点了,如果你再把C和E连起来,他们的重点又是F,这样就会重合,就会构成回路,这就是判断回路的。
17:03
一个关键。对,就说你把这条边加进去过后,你会发现C和E的重点还是F,那么就重复这就什么,这就是判断回流方式,也就是说听这句话特别关键的一句话,各位没有。我们加入的边注意听这句话啊,我们加入的边的两个顶点不能都指向同一个终点。明白吧,否则就会构成回路。就说你加入的这个C和ec和ec和E,他他们现在呢,他们现在追星,他们现在呢,已经在没有加你这条边的时候,其实他们已经都指向了F,如果你把这个C和E。再加,因为你就说他这个判断是当我们还没有加,就说现在你准备加CE之前,你要判断判断一下C的终点是什么。
18:05
E的终点是什么?你现在在没有加C和E的时候,C的中点是f fe的终点也是F,它们是指向同一个终点,这个时候这在这种情况下C和一就不能加入。C和一就不能加入,明白这个意思了吧?诶就是这句话,就说我们加入的边的两个顶点不能同时不能都指向同一个终点,因为你现在已经指向了这个同一个终点,你如果再加,你再把这个C1加进去,他两个已经是了,就没办法了,那有些同学说老师那你刚才为什么可以加呢?因为在刚才加这些边的时候,他们还没有指向同一个终点。所以说就是道理。明白我的意思再说一遍啊,就说你在加任何一条边的时候,你要判断现在这你加的这两个边的两个顶点是否已经指向了同一个终点。如果是指向了,就不能加入,否则才能加入,比如说我们再再举一个例子,那为什么这个也不能加入呢?C和F也不能加入呢?
19:07
为什么这条边C和F这条边其实还是比B和F要小吗?是不是这样子的,是不是样子的?OK,但是你想一想,你C这个时候,你如果真的加这条边的时候,假如这条边加的时候,是不是C在没有加这条边之前,C已经指向F了,而F本身也是它的终点也是F,是不是也违反这个规则?对不对,那为什么B和F这条边可以加入呢?各位同学,因为你在你在加,你在还没有还没有加这条边之前,F的终点是什么?F的终点是F没有问题,但是B的终点是谁啊,你还没有加进来B的终点,你没有加之前,它B的终点没有终点吗?如果说你一定要看一个终点,他就他自己了,如果他自己一个点来看的话,所以这个时候你在没有加的时候,这个B呢?OK,他还没有这个终点呢。
20:02
所以说这个B和F这边是可以加进去的,当然你加进去以后,各位朋友,你把这个B和F加进去以后,那么B的中点也指向了F。明白这个意思了吧,因为它它加进去以后,这不就联通了吗?连通了,那连通过后,F仍然是它最大的一个,最最大的这个这个顶点是不是,那这样加进去以后,B的顶点也B的顶点对应的终点也是F了。明白这个意思了吧?OK,好,这个道理我就先说到这里,好不好?我觉得大部分同学应该能听懂,也不是特别的难。好了,那关于克鲁斯卡尔的图解,它的算法思路就给同学们讲到这儿,一会儿呢,我们用代码来实现克鲁斯卡尔对前面这个公交站问题的求解。OK,关于这块,我们先说到这里。
我来说两句