00:00
OK,那现在呢,我们来在迷tree里面,我们编写这个普算法,编写就是。编写。编写一个prime。Prime算法。Prime算法,OK。生成什么呢?生成最小啊,得到得到最小生成数。OK,那现在开始写这个方法,Public void p,那你你让我生成这一个数,你首先得把这个图给我,对不对,我把这个图先拿到对吧。下一个还要把什么给我呢?把你这个顶点给我V,我先做一个注释,就说你得告诉我你是从哪个顶点开始来生成这一个最小数。这个大家能理解吧,这是图。这是那个图很好理解,这个是表示从图的第几个第几个顶点。
01:05
顶点。顶点开始生成。开始生成,比如说你要从A这个顶点,大家想A这个顶点它对应的下标为零,那你这就应该给我传一个零进来。明白意思吧,那如果你要从B这个顶点生成呢,那你就给我传一个一,依此类推,但是你不管用哪个顶点呢,最终生成的这一个最小生成数,它的权的权的总和应该都是25就是对的。好,那有了这个算法,我们就开始来玩了吧。好,现在呢,开始来玩一把。我们,我们开始第一步。第一步,首先我应该怎么写呢?大家看我先六一个int,一步步来,好同学们grab。点vertic这句话是在做什么呢?我们先把这个代码写去了,写起来,然后呢,再给大家做一个解释。
02:07
这个地方六一个六一个int,然后我们这写一个什么比较合理呢?来写一个visit。Visit就代表已经访问过的,对不对,我得一个这个东西。好,这个是这个一位数组的作用是这样子的,干什么呢?Visited这个数组听我说表示,哎,表示什么呢?表示或者是标记。标记标记什么呢?标记节点,节点或者我们这叫也叫顶点对不对。叫顶点是否被访问过,因为同学们根据刚才我们的一个思路,是不是他如果访问过我,我们我们在下一次进行便利的时候,就不能再去找他这个关系了,是这样子的吧,所以这个visit的呢,很visited很很有用,这是第一步我们要做的,现在我开始便利。
03:05
啊,这个就V的初始化都为零,注意把这句话写上啊,这个数组在你没有变历的时候,它默认都为零,代表都没返问过对吧,默认它默认元素的值都是都是零。啊,表示没有访问过,没有访问过,但是你不同的编程语言呢,你要注意有些编程语言它默认不是零,或者有些编程语言要求你必须初始化,你自己在负循环一下就可以了,明白意思吧,就这句话呢,你可以不写,就这句话你看根据不同的语言来说呢,可能有些语言就不需要写了,比如说我要写的,我这样写的graph。点什么呢?Ver ver verex,然后I加加ver,然后这边写完过后呢,如果说我这样写,大家看能否看懂等于零。对,这叫初始化,如果是Java里面其实你可以不写,因为Java本身默认它就是零,所以说上面这一个功能你可以不写,但是实际上有这个流程哈,有这个流程好,那下面我们紧接着继续写吧,那先把当前当把。
04:17
把当前这个节点标记标记为一。已访问,OK,非常的简单,Visit,那么这个下标就应该是你传递的V写成一,我们用一表示已经访问,大家知道这意思吧,好的,那有了过后呢,大家看。我们在进行这个变历的时候,是不是我们会把这个EF记录下来,那么我得用两个变量来标记这两个顶点对应的。下标好,所以说我先写一个H1等于负一,待会儿我做一个解释,H2也等于一个负一,这是有什么作用呢?注意听。
05:02
用H1和H2干什么呀,记录哎,记录两个两个顶点的下标,理解了啊,就待会呢,我我两个顶点,因为我到时候要打,我我我不知道是哪一个顶点,我就用这个下标来找他,明白意思吧,OK,非常的简单,那现在呢,我们再来初始化一个mini位。Mini,我初始化为1万。有初始化就是一个最大值,那么在便利过程中,这个mini肯定是要变化的,就是我初始化一个比较大的值,将这个mini先初始化,初始成。一个叫大子大树。大树后面呢,后面在便利过程中,过程中会会被什么会被替换,也就是说只要有一个位,有一个全路路径的长度比我这个小,我就替换它,所以说我故意设了一个比较大的数叫1万。
06:09
OK,当然你要是写的再大一点也是可以的,也是可以的,OK,那这写完过了,我们现在开始for循环。In ti,注意听零,我们现在怎么写呢?我写个K。1K小于我们这个图的顶点的个数vertex。S,然后K加加。这句话什么意思,就是我会变,我会生成多少条边呢?我会生成,如果你有N个顶点,我生成的边应该是N减一,那也就是说因为因为有注意听啊,这个稍微有点绕,因为有这么多个顶点。是不是同学们有这么多顶顶点,那么我们我们会普里姆,普里姆算法做完了以后,普里姆。
07:03
普里姆算法结束后。结束后有多少条呢?有这么多个顶点,减一条边是不是减一边,因此我在这写的是从一开始遍历的,所以它一个会进来。graph.vertex减一次,那就会产生这么多条边,明白了吧?好,那下面这个代码呢,我们继续来写。这个代码我先把代码写写一下好,还是一个破循环,I等于零,I小于graph。点vertexs,然后I加加。然后再写完啊,For循环NTJ等于零,节也小于grab什么呀,还是ver,然后结加加。我我只有把这个代码写完了,我再回头来说,你们才知道这什么意思,其实这个过程就是刚才老师说的,找到一个顶点,便利他所有的,但是你要考虑将来你这个这个里面有多个,比如说你这个这个是有AGB,那你要便利AGB里面。
08:19
就是便利这个集合里面的所有顶点的所有相邻边,明白我的意思吧,所以这有一个双层负循环,就这么来的,那这么应该怎么写呢,大家看。我先我先把这个条件写完,不然的话不好讲啊,比如说这个顶点已经访问过了,I被访问过了是等于一的。一并且呢,并且慢,不要着急啊,Ver解它是没有被访问过的,诶大家大家看着看着老师要要写什么,并且还要表示graph。他的这个wait wait。啊,哪哪一个位置呢,就是当前的埃及这个位置。
09:03
OK,不着急它干什么呢?它小于你认为的最小这个全值,在这种情况下我们要去替换。替换什么呢?Mini好不着急,这个地方大家一时半会看不懂是正常的啊,我一会儿就会解释,就gra。什么呢?OK,那就是我们的I。点啊,忘了写点的位置,它的I和节好,大家大致看出来是什么意思了吧。可能有些同学比较聪明的同学呢,已经看出来这句话的含义是什么呢?大家知道这句话在做什么吗?好,我给大家做一个注释,你们有没有发现这一句话是在便利他已经访问过的节点,而这句话是在便利他所有没有访问过的节点,而这个依附条件是在判断我这个访问过的节点。是不是正在和一个没有访问过的节点进行进行探视,同时满足当前这个节点的全值小于这个最小值的时候,我就干什么呢?我就去。
10:07
把真正最小的圈子记录下来,并且进入他记录下他的这个顶点的他的两个下标,呃,有点绕,是不是很不着急啊,我在这写一遍,我一一会大家知道了,对吧,这个是确定,注意听它是在确定什么呢?确定每每一次都听每一次生成的指图。这个子图就是同学们刚才跟你分析的,像这个就是一个子图,这个呢也算是一个子图,明白了吧,他在便历每一次生成的子图干什么呢?和和哪个哪个。节点,哪个节点的距离最近?那我怎么样才能得到?最最近啊,最近我怎样才能得到一个最近呢?所以说大家看下这个地方这个I这个。
11:07
I是什么意思呢?这个I其实它是I顶点。II顶点或者I节点啊,I节点,I节点表示被访问过的。顶点。啊节点节点就咱们就统一都叫节点,而这个节表示什么?节的这个节点,节点表示还没有没有访问。访问过的这个节点。但是你在便利的过程中,你并不敢保证哪个是被访问,哪个没有被访问,也就是说从你的这个逻辑上来讲呢,你认为我先。便利这个访问过的,再去让访问过的节点和每一个没有访问过的节点进行比较,但实际上你这样假设不一定成立,因为你的随着你不停的便利,肯定被访问过的越来越少,被访问过的越来越多,所以说下面有个判断,就是说当VT的I等于一的时候才是。
12:13
这个我们假定的这个I被访问过才是真正成立的,然后同时满足我再去对这个I。这个I定下来过后再去看它每一个节没有被访问过的明白吧,就相当于说我找一个顶点A,我就按照这个A去干什么呢?去跟它相连的每一个顶点进行比较,呃,判断说我已经被访问了,你访问过没有,你如果没,你如果还没有访问过,好,我再看你的这个距离是不是一个。比我当前假定的这个圈子还小的,我就替换他。是不是,那这样子是不是每再一次负循环,我就找到了这个生成的子图里面哪一个是最小的。
13:00
那个那个路径同时还把它的节点的I和节,把它节点记录下来了,明白意思吗。啊,我不知道大家听懂没有,就是这个一个for循环,这个双层for循环的作用就是一个,就是去确定每一次生成的子图里面的哪个节点距离是最近的。那么我怎么才能得到呢?我就去便利每一个节点。因为我不知道这个纸图哪现在有哪些了,所以说我便利这个。整个这个图里面所有的节点,我假定I是被访问过的,其实没有被访过的,然后我通过这个条件来确定是不是这样子的,最后通过一番便利,我就拿到了这一次纸图里面。这次组图里面哪个节点,哪两个节点之间是最近的,应该是哪两个节点啊,应该这样写,哪两哪个节点和和这一次的应该是哪个节点,和这一次便利的这个节点距离最近,我就不写了,这个大家一定要去理解啊,我很难理,这个不好描述。
14:03
好,那这个替代mini的作用是什么呢?就是我把这个再写的清楚一点,看看大家能不能理解,就是寻找。他这个是在寻找什么呢?OK,寻找已已经访问过的节点,访问过的节点和未访问未访未访问过的节点。节点。访问过的节点间,节点间的全值最小的边。哦,就是针对这一次啊,针对这一次好,那大想经过这个for循环处理过后,如果我们这个for循环结束以后,我想问同学们一个问题,我想问同学们一个问题,此时此刻是不是这次我们就找到了一条边了。也就是说,当退出这个负循环时,我们就已经找到了。是不是就。
15:04
退出这个平方式,找到了一条边,找到一条边是最小的,能理解吗?那我就把它打出来,大家看一下就可以了,注意听讲好,我就写写了啊边。边把它打起,打上等于什么呢?这次的点。好把它这个顶点找出来,H1是它的第一个顶点,再加上。对,再加上我们来一个逗号。逗号过后,我们再把第二个顶点也给同学们打出来,就贝塔几呢,H2是不是第二个顶点好,然后我们再加上一个。这样的回回来一个值,然后再写上全值是多少,全值写个冒号,加上我们这个mini。代码就写完了。那么写完以后,同学们,我们还有一个特别重要的工作要去做。要把。
16:05
当前这个节点就是你找到H1H2这个节点,标记为已经访问过了,对不对?那么将什么呢?将当前这个。找到的节点标记为,标记为已经访问。访问,那怎么来标记呢?各位朋友,其实非常简单。你为题的。微体的谁要H几呢?H2就是一,那为什么是H2呢?因为你在整个这个过程中,是不是你这个I是没有已经访问过的,而这个节你是代表没有访问,那相当于说你真正找到的节点是你已经访问过的这个I,这个节点和没有访问过这个节的节节,这个节点的一个关一一个关联,就有点类似于这种感觉,同学们听我讲哈。就好像你你在找这个,找这个G的时候,你在找这个G呢,就有点像这个I,因为你在不停的变,最后你找到哪条线了,找到。
17:03
B这个B就是结这个二,这个节呢,你是放在H2里面的,明白我的意思吧,所以说你在这个地方呢,应该把H2对应的这个下标的元素制成一,代表已经访问过,访问过过后不要忘了你的mini要重新制一下。代表第二次寻找,因此要把这个重置。要重新。对重重新重新设置为一,设置为一个最大值,最大值。最大值。OK,那就是1万。就是1万好,那我们把它设置成1万,怎么写呢?直接写个1万代码就写完了。同学们,代法就已经写完,到此为止,我们这个普里姆算法就写完了。那代码对不对呢?不知道,我们试一下吧,同学们,现在呢,我们进行一个测试,普里普里姆算法。
18:01
OK,那现在呢,我们用mini第二谁啊,我们的这一个。P,那把图放进去,我们从第几个地点呢?从E,如果这个地方没有任何问题的话,那么它应该给我们显示的结果应该是AG。应该是,它应该是第一条是AG啊,也就是AG是第一条线应该是AG1,这边应该输出的是GB3啊,这个这个是二,呃,这个路径是二啊,因为AG他们之间距离是这个嘛,那第二个又应该输出的是GB3,第三个应该输出的是G。GE4,第四个是EF5FD,下一个是FD4,呃,FD4,再下一个就是ACC是几呢?AC是七。AC47,好朋友们,我们运行一下,看看结果跟我们想的是否一样啊,是否一样,这个我不敢肯定,但是呢,我们还是要有信心走一个运行。
19:06
好,运行过后我们看一下这个结果,我们想的还真是一样的,看234547没问题吧,那整个值整个全值加起来是多少呢?就是这个是五五加499加五十四十四加四等于十八十八加七二十五正确。正确没有问题,好,那有些同学说了,你换一个顶点呢,比如说我从一这个顶点,那这个时候从就从B这个顶点开始来创建我们最小生成数,那这个时候我们再来运行一下。诶,你看它也能生成,但是这个顺序就有有变化了,同学们看一看对吧,顺序肯定跟我们刚才不一样,但是你发现它的全值加起来仍然是25加一下三加二得五,五加四得九,九加五得十,44加四十八十八加七,25正确。正确,好的,那同学们,这就是老师关于这一个普里姆算法的讲解,大家看理解没有,如果你还没有理解的话,很简单,你下一个断点跑一圈就可以了,并不难。
20:08
并不难,只是这种算法题呢,讲起来吃力在什么地方呢?就是不好描述,你看三层负循环。三种波循环里面呢,这个I和节呢,它是假定他没有访问过,但是实际上里面加了一个if,还要判断到底是不是真的访问过,还是没有访问过,我再去判断你的全职,也就是说他每次这里面你你就是认为他每次要确定上一次的生成那个纸图。里面的哪个节,哪个节点是哪个节点和哪个节点之间是距离最近的,把它扔到我们这个指图里面,指图里面去,再下次这个指图又变大了,以此类推。说这个情况呢,要深刻的理解其实代码就不难了,好吧,OK啊,那我这会我就不再去啰嗦了,我再不再debug了,相信大部分同学应该能够看懂,看不懂的同学把这个代码多看几遍,多敲几遍就可以了。来,同学们把刚才老师讲的图里姆算法给大家进行一个小结,来,我们看看我们怎么讲的普里姆算法来玩一把。
21:12
那么我们怎么讲这个普里姆算法的呢?首先呢,我们仍然是通过一个问题引出了这个普里姆算法,是不是同学们。我们怎么引出,先提出了一个修路问题,让大家看了一个应用场景,最后呢,这边有一些要求。是不是这边我们提出的要求是,诶,你能不能完成这样一个。需求,那么这边是我们一个最朴素的一种思想,就是最简单嘛,那我就把四角边全部连起来,但是这样做后果很严重,对吧,你把私要连起来,试连起来了,但是。你你也浪费资源了啊,对不对?人家要求只要连通,并没说条条道路都要通罗马嘛。对不对,好,这是我们的这个图。
22:01
就是你不能说把每条边都连起来,你每条边都都都可以,那大家都太高了,好,这是我们提出的第一个。事项,那紧接着呢,我们就给大家解释了何为最小生成数,是这样的吧,也就是说刚才提的这个问题的本质,它其实就是求最小生成数的。这么一个问题,那在此呢,我们就给大家介绍一下何为最小生成数,然后呢,这边我们举了例子给大家聊了一把,是样子吧,同学们,诶,就这样子的,没有问题。那这地方我们也提出解决最小生成数的算法,一个是普里姆,一个是克鲁斯卡尔,克鲁斯卡尔呢,现在我们没讲对不对,没讲这边有有些图你给他拿过来。就是。给他演示了什么叫完全图,什么叫生成数的概念,而我们最小生成数就是要保证它能够在这种情况下它的全值之和是最小的,就是最小生成数,那把这个讲完了以后呢,我们又给大家讲了一下普里姆算法的一个步骤,是不是同学们?
23:09
这是普里姆算法的一个步骤,OK,那具体来说步骤呢,就是老师在这给给大家理出来的,但是我也讲了,如果仅仅靠文字来理解,我相信大部分同学是很难理解的。至少我看到这个文字我是很难理解的,对不对,于是乎呢,我们就图解了一下普里姆算法,是不是用图解给大家讲了一下普里姆算法,那具体来说就是用这一段方式来聊的,那怎么走的呢?诶第一步怎么走,第二步怎么走,第三步怎么走,讲的很清楚。是不是也说你找到DA点,找到过后再把E点找到,再把E点找到过后,再去在A和E的基础上再找到B点,再然后在ABBG3点面找一个跟这三个点里面最短的一个路径。算法就这么玩的,明白了吧。
24:00
有,它总是这样子找的,找到一个子图,然后再找下一个。哪一个剩余的那些没有访问过的节点和我们子图里面的哪一个节点是最近的那条路径,就把这个找到节点再加到我们子图里面去,这是它的核心思想。这是他的核心思想,OK,那这个讲完了过后呢,我们就给大家整了一把。代码实现是不是就把代码给大家跑了一遍,那具体来说呢,就是我们的一个思路。好,把图放到这里来。图呢,我还放这儿同学们,便于各位同学今后的复习,是不是同学们这算法不好讲啊,算法确实不好讲。就是有时候你明白了,但是让你让同学们明白还是挺费劲的这事,那么代码呢,我给同学们。给大家放到这里,好吧,各位扔到这里了。
25:01
好的,同学们,那关于我们普里姆算法就给大家讲到这里。
我来说两句