00:00
同学们,我们来看一下普里姆算法的他的一个思想是什么样子的来看。普里姆算法是求最小生成数,也就是在包含N个顶点的连通图中找出只有N减一条边包含所有N个顶点的连通子图,明白这意思,也就是所谓的极小连通子图。那么这个绩效联通指图在实际的我们应用中还是非常有价值的,比如说刚才我们说的修路问题,它就非常有价值,比如说你一个城市,一个国家怎么去让各个城市联通,并且它的总里程数又小,这样就可以节省我们的人力和物力,是这样子吧,同学们。那么普里姆算法具体的思想是这样子的,同学们看,首先它设置设计为一个连通图,T为最小生成数,V是顶点集合,ED是边的集合。那这块大家可能听起来有一点吃力了,不要着急哈,待会儿呢,我会用画图的方式来了解,你们先听一耳朵,若从顶点U开始构造我们最小生成数,那么这个顶点U呢?你可以自己去选择,你从第一个顶点还是第二个顶点都OK。
01:10
因为你不管怎么选择,最终你生成的最小生成数的全值的总和是一样就可以,则从集合V中选出顶点U放入这个集合中,也就是说它是从第一个往里面放进去,然后依次让这个集合变得变变得是那个是越来越多标记顶点V为已经访问过。若集合U中顶点。UI与集合V中的顶点V结之间存在边,则寻找这些边中全值最小的边,但不能构成回路。OK,将顶点V节加入集合U,看,又加进去了,原先是不是只有一个U啊?现在又把V结加进去,然后将边UIV节加入集合D中。标记成又被访问过,那么重复第二步,一直重复,直到V相等,即我把所有的这个顶点都变离到G,就是这句话。所有顶点都被标记为反问过,那么此时D中就会有N减一条边,这个时候就结束了。
02:13
那同学们看,刚才老师讲这个1234 1234这个步骤呢,我相信很多同学也很难理解老师在说什么,因为他比较抽象,对不对?那么我这也有提示,单独看步骤很难理解,待会通过代码来讲比较好理解,在讲讲解代码之前,我们呢,仍然用图解的方式先给大家说一说,来打开我们的,还是以这个图为例,打开这个地方,我们来跟大家聊一聊。我们就一个叫做普里姆算法的一个图解分析,写到这吧。叫普里姆,普里姆算法的图解分析没问题吧?同学们,那到底刚才这段话说的是什么意思呢?OK,各位同学请看老师的思路。
03:03
来假如,我说假如啊,现在呢,我们是从A这个顶点开始进行处理的,或者从A顶点开始来生成我们最小生成数A这个顶点,那么我们。第一步。我这样写好吧,第一步从A这个顶点。零点。开始生成,开始处理。那么这个时候这个A顶点,同学们想想A顶点现在能够它它能够访问到,或者它能够直接连的是不是,是不是只有一个C有个G有个B,能理解吧,那就说A可以跟谁连的,注意听讲啊,A和C它们之间是可以连的,差它的全是七,看清楚没有A和。G是不是也可以进行一个连通,它的全值是。
04:02
全值是二,看到没有,然后呢,A和B看清楚了,A和B跟谁可以连,跟AAB可以连,它的全值是五,那大家在想此时此刻能够跟跟这个A联通的最小的是不是G?于是第一次处理完了过后,我就已经得到了一个。一个集合,原先最先前只有这个A在里边,经过处理过后,我发现目前能够跟A进行连通的实际上是G这个顶点。那么全值最小,于是这个就变成了AG,看清楚了没有,好,紧接着第二步来了,各位朋友,第二步现在呢,又以这个为一个图子图,以它为一个子图,那么又开始处理,那么这个时候它的处理方案是什么呢?注意听讲,它是让这个A和它能够连通的,并且还没有访问过的顶点进行处理,再说一遍,让A和它能够直连,直连的顶点。
05:06
并且这个点还没有被访问的,进行这个进进行这个这个处理,那也就是说现在开始什么呢?将A和B顶点,顶点和它们相邻的。相邻的还没有访问过。访问。的顶点。顶点进行这个处理,那怎么处理呢?比如说A,现在跟A相连的还没有访问过的,其实就是B点和C点,是这样子吧,那就是AC,还可以告诉别人是七个点啊七它的全值A和B,各位同学是不是它的全值为五,但是这个时候B,哦,说错了啊,这是G,刚才说错了,不好意思,G。将A和G顶点和他们相的还没有反过的顶点进行这个处理,那么我问大家,G现在就是你们看到的这个G,它能够相邻的还没有处理过的顶点有几个,A是不是已经相邻,但是他已经处理过了,就不能再处理,那么B是不是没有处理过,于是我们现在又找到。
06:15
G。G它跟谁是相连的?跟B是相连的,它的全值为三,是不是G跟谁?跟这个E是相连的,它的全值为四,看到没有G跟谁呢?G跟F是相连的。它的全值为六,各位同学请告诉我,在我这一次进行处理过程中,哪一个边是最小的,是不是就是GB呀?各位朋友,是不是就是GB。于是乎,我们又把。在这个子图里面又加入一个新的好朋友,所以呢,就是B又加进来了,也就是说原先A是一个子图,现在变成了AG,又变成了AGB,紧接着同学们下面思路继续,我再写一个,我后面就不写了,同学们注意听,然后呢,再以同学们看到agb开始。
07:12
啊,将A。将AG。B顶点。顶点和他们这句话我就翻过来。进行处理。好,这边当然我们就这写个箭头啊,那么将AJB顶点和他们相邻的还没有访问过的顶点进行处理,那我问大家A相邻的还是谁相邻的是不是还是有C啊,各位朋友是不是七还是要写到这的,A和BABAA和BA本身是相邻,但是B是不是已经被处理过了,它已经加到这这个子图里面来了,所以B不能再再去处理,和G早就处理过了。好,我们先看GAGA相邻的还有这个E没有问题,它是几呢?是四。
08:00
G和B已经处理过了,不能再写了,G和F还没有处理,说G和F注意听讲啊。GF现在他的全子是不是六啊,好,现在还有一个好朋友B也进来了,那看B相邻的有哪些,B跟谁相邻呢?B跟A相邻,但A已经访问过了,你就不能再再去访问它了,因为它已经已经加到这里面来了,你不能再去处理了,那B跟G也处理过了,GB跟D,只有B跟D了,它的全值为九,各位朋友请告诉我在第三次处理里面,哪一个边是最小的,或者全值是最小的,是不是我们的GB,这时我们就在这个基础上,各位朋友。各位朋友,我们是不是又把通过这个EGEG这个流程把我们的E又加进去了,是这样子吧,比如说这个时候我们这个子图呢,又加入了一个新的好朋友。所以啊,就是我们的一。
09:00
当然这个地方你是可以记录下来这个E是哪一个顶点给它进行相连的,我这简写了一下,就是这个E,你因为你前面有AGB嘛,那这个E是谁跟它相连呢?是be还是E?E记呢,啊,这个就要跟待会我们在程序里面可以提出体现出来,我我不知道我说清楚没有,就说你现在加了个E顶点,那这个E顶点是ae跟他连的,还是GE跟他连的,还是B跟他连的呢?这个在程序里面是可以得到它的一个一一个一个结果的,但是我们放到这里面就体现出是A。G。Be,好,下面四五我就不写了,那么455步我就不写了,最后这个结果是什么啊,后面点点点。点点点,就每次都这么去处理,每次这么处理,最后这个结果是什么呢?我这里已经给大家准备好了,因为这个推导过程呢,也很简单,我就不去写了,大家看我已经推到这儿了,那后面还有这个第四次,第五次,第六次。
10:02
好,那后面呢,这个流程大致就是这样子的。看。到了下面AG de,然后第四次循环,第五次循环处理,第六次循环处理,各位同学。那么同学们可以看到,当我们把第四次处理完了过后呢,这个EF又加进来了,全值为五,到第五次的时候呢,OK,那么这个时候D又加进来了,对不对?就是四,这个四是FD之间的关系,FD就是这条线,那么第六次循环的时候呢,把这个CU加进来了,就第七次,同学们可以看到此时此刻经过我们这一番处理。经过我们这番处理,我们一共有几个点,我们一有七个点,是不是全部都加到,那这个做完了以后,应该最后得到的这个结果就他了,同学们最后得到的结果就是这样一个。这样一个集,集合什么呢?各位朋友,就是这个,最后这个加进来的就是我们C。
11:08
那这个时候一共有几个顶点,1212345。一个两个三个,四个,五个,六个,七个,七个一共有几条边呢?同学们看,七个一共有几条边?我有七个点,七个点1234。一二。1234。567啊,中间还有一个G,刚才忘忘少数了,对吧。那都进来了,我用七个点,七个点我一共有几条边呢?六条边满足我们最小生成数的最基本的要求,到此为止,这个思路就就理解完了,也就是大家要明白它是怎么怎么玩的,我通过第一、第二、第三次已经大家讲清楚了,看到没有?也就是说普里姆算法的基本的核心思想就这么一点,我们有七个点。我没有区别,那么最终呢,我们会生成六条边。
12:01
六条边,其实这已经就已经告诉你,一个是AG,它的AG这条边是二,全值为二,那么第二个是第二个是这个GB,这个它的全值是三,而最后这一次是EG,它的全值是四,其实现在你可以算出来总总公里数应该是多少呢?就是二加三再加四。再加上后面的这几个,就是二加三得五,再加一个四得九,九,呃,九完了过后。九完了过后再加一个五就是14 14,再加上这个全折加四就是18 18再加上最后一条边七加七就是25,也就是说如果按照我们这个普里姆算法的一个规则的话,我们整个真实要去连的这个路径应该是这几条路径,一个是AG。我用一个红色的线给它标一下AG要连起来。
13:03
这条线我们要修,这条路要修,然后呢是我们的G和B,也就说这条线这条路要修,然后呢是我们的E,呃,GEGE是这条边要去修。好,然后呢,是我们的EE就是这条这条路要修。然后是我们的FDFD是这条路要修,然后是我们的AC,这条线要修。也就是最后这条整个修的路径是一条两条,三条,四条,五条,六条,而且它是联通的。它相互连通,极小连通图,那么我们总共需要花25公里,就是我们要修25公里,大家看它避开了最大的759。六是不是避开了?诶,但是有些线你是无法避开的啊,诶这个为什么是八呢,这条线是是写错了吗。
14:00
这条线AC好不好意思啊,这条线我这画错了,ACC这条线啊,我说怎么会多一条线啊,这样就对了,AC,我刚才说这说的是AC,那画成ec了,是这条线,同学们不好意思啊,AC这条就AC。嗯,这几条线那加加起来过后呢,你们你们可以看到一共是25公里,同学们,这就是普里姆算法的一个图解分析,大家看听明白了没有,那这个听明白过后呢,一会儿对,一会儿呢,我们就把这个代码给朋友们实现一把,OK,好。这个图我先给大家,呃,这个就就待会给他截个图啊,这个图应该是这画的,也是比较清晰的截个图。
我来说两句