00:00
同学们,我们继续来讲下一个算法,叫做普里姆算法。那普里姆算法是什么呢?我们仍然是以一个应用场景展开对普里姆算法的讲解,大家看这有个修路问题,说现在呢,有七个村庄,分别是ABCDEFG7个村庄,那么这七个村庄呢,现在有一个任务就是需要把修路,把这七个村庄连起来,连通,连通,那么各个村庄的距离呢?它这有个边,代表他们的距离,你比如说A和B这两个村庄,AB这两个村庄,他们之间的距离为五个公里,注意。这个五代表他们的距离,并不是说他这个路已经修好了啊,就是现在就是问你这条路要不要修,只是距离,人家告诉你了AB这个地方的距离为五公里,给了你这个条件,那么现在呢,就是问如何修路,保证各个村庄都可以连通,并且修路修。
01:00
并且总的修建公路总里程数是最短的,就是这个问题,大家想你拿到这个问题,你会怎么想呢?大响,你会怎么去思考这个问题?最简单的是不是现在人家已经把各个边告诉你了,你就把各个边全部连起来,比如说这有一条边,两条,三条,四条,五条,六条,七条,八条,九条,十条,那你第一个就是你把这十条边连起来,对不对,将十条边。十条边。连接连接起来即可,连接即可,但是这样子你肯定不能保证它的总的这个修建里程数最短的,但是但是它的里程数总的。李晨。里程数不是最小,显然不是最小,你都已经把它全部连起来了,那怎么可能是最小呢?因此我们这个地方要解决的问题就是你哪些路该连,哪些路不连。
02:04
而且还能保证ABCDEFG它是可以连通的,就是正确的思路应该什么呢?正确。就是。正,正确的思路。思路是尽可能注意听,尽尽可能的。尽可能的选择少的,注意听少。少的路线。少的路线,尽可能选择少的这个路线,并且。并且每条每条路线最小。最小,哎,你要这么去选,从而才能保证怎么保证。保证总里程数。总里程数最小。什么意思呢?就是说你尽量选少一点路线,比如说你一共有十条,我就选七条或者选六条,看看行不行把它连通。
03:06
对不对,第二个呢,就是说你每条路还要尽量选最小的,比如说你选了七条线。而且你要保证这七条线里面是你能够连通的里面。这个路线最小的。一个是要少,一个是要小,这样你才能保证总的里程数是最少的,对不对,这应该就是最少了。大家明白我在说什么吧,诶,其实我们要是正确思考问题就可以,那么这个问题就是刚才我说的这个所谓的正确思路,它转换到我们这个算法里面,它就应该变成了什么一个问题呢?各位同学请看。刚才我们修路的问题的本质其实就是最小生成数这个问题。就是你怎么让它生成一个最小的最小生成数,那么最小生成数呢?我这里有必要先给大家介绍一下何为最小生成数,叫minimum costs spning tree,简称mst。那么它是什么意思呢?同学们看。
04:07
他的意思就是说给定一个债权的无项。连通图就是一个无相连通图,带全。如何选择一棵生成树,使树上所有的边上全的总数最小,这就叫最小生成树。那么最小生成树它有什么特点呢?第一个,假如它有N个顶点,那它必须要有N减一条边,也就说刚才我们有七个村庄。刚才我们有七个村庄,那你至少要有六条边,你才有可能把它连通,明白。那么第二点呢,包含所有全部顶点,因为你要连通嘛,那肯定就要所有顶点都要连,都要包含在里面,N减一条边都在图中。哎,你N减一条边都在读,举例说明,你比如说同学们看这张图。这是一个图,叫完全图,完全图,这是完全图,那么这个完全图如果按照树来生成的话,这个就是一棵树,这也是一棵树,这也是一棵树,为什么呢?他们是可连通的,什么意思?你比如说我从这个A这个点出发,我可以到任何一个点,比如说到这,到这,到这,虽然这个点我不是直连的,但是我可以通过这两个顶点到达它。
05:22
诶,他也算是到达明白我的意思吧,就好像你从北京到成都对不对,没有北京到成都直达的,你经其实你你是要经过一些站才能到到到成都的,是不是同样这个也是一样的道理,这个也是。是不是比如说这个点我要到这,我经过这个点就会到,如果我从这个点要到这个点,我也可以经过中间这个点,估计其他也一样的道理,所以说这个呢,就是叫做生成树,只是我们现在要研究的是怎么样这让这棵生成树是最小生成树,明白这意思了吧。那么求最小生成数的算法呢?目前来讲,最经典的一个是普里姆算法,一个是克鲁斯卡尔算法,这两个算法呢,我都为大家讲解。
06:08
好的同学们,那关于普里姆算法的一个引出就是,其实它就是要解决最小生成数的问题,那关于最小生成数我们就先给大家介绍到,介绍到这里,那么一会儿呢,我们就来介绍普里姆算法,它到底是一个什么样的算法。然后我们再举例完成前面的这一个修路问题,大家就很清晰的明白了。呃,Po算法其实并不难,同学们并不难,它没有前面我们讲的KKMP算法那么绕比较还是比较直接比较简单的,OK。那么关于具体普里姆算法是什么样子的,我们下面为大家讲解。
我来说两句