00:00
同学们,我们来完成最后这一段代码,就是完成用克鲁斯卡尔算法来生成我们的最小生成数,那开始写代码。Public。VO克鲁斯卡尔。然后这边我们名字方法的名字呢,咱们就取这个名字吧。K。克鲁斯卡尔。然后我们来一起完成,首先我们先定一个变量index。初始化为零表示什么意思?说一下这个是表示表示最后这个结果,哎,最后结果数组的索引。也就是将来我我我得知道我这个结果数组里面有多少条边,那么我这用index表示它的索引,第二个呢,我们来写end。大家还记不记得我们在前面有个N数组?
01:03
这个呢,先要把它初始化一下,它一共有多少多大呢?就是我们age number这么大,我写个注释用于保存,保存什么呢?保存这样写保存。已酉。已有生成素已有生成素。好的,接着。嗯,用于保存,什么叫用于保存已有。已有最小最小生成数。最小生成数干什么呢?中的每个。每个顶点,顶点它在在什么呢?在最小。最小生成数。中的终点。中的重点,因为我们刚才不是讲过吗,就是你在。
02:03
你在想把一条边加到已有最小生成数这个结果数组的时候呢,你得判断你准备加入的这两两,这个边的两个顶点是否已经在最小生成数,它们终点是否相同,所以说这个N就是要保存,也就是说将来我们在这个地方。在这个地方会会传进去的N字。就这个东西明白了吧。啊好,接着继续往下写。在哪去了,刚才在这接着往下继续完成,那下面呢,我们是不是要去得到我们先这个结果,数组是不是我们来创建。对,我们来创建结果。结果。A,结果数组就是将来我们就是,也就是说这个结果是干什么呢?保存我们最终的最后的最小生成数。
03:02
OK,那这个应该怎么写呢?就e data塔,它肯定是一个边的集合嘛,是一个数组嘛,所以说用e data这个数组来存放,我取个名叫result results等于六个e data那。那多大呢?诶,这个数字将来要有多大呢?同学们显然就应该跟我们这个边的数目是有关系的,所以说这把它先创建起来,创建起来过后,我们现在呢,来先获取图中。就是原始的这个图。就是原始图啊,就是图中所有。所有的边。的集合。那一共有多少天门呢?理论上说,呃,不是理论啊,一共初始的时候一共。一共有12条边。
04:01
呃,为什么有12条边,大家可以去数一数。你你数一下,你把这个原始的这个图你数一下,一共有12条边啊,一二三四五六七八九十,十一十二,正确的12条边,那这12条边咱们是怎么得到的呢?是不是我们本身已经有这个方法了呀,还记得吧,还是e data。那这个边呢,我们就叫eaa。Ages等于什么呢?同学们。De等于。没问题吧?A知识get a知识就拿到了。那拿到这个东西过后呢,我们可以在这儿可以给同学们这个地方就不去测试了,如果同学们愿意的话呢,可以在这测一下,我们是不是12条边,我们可以简单测一下,就是我们看看拿到的边是什么获取。图的边。边的集合,我们可以把它输出来看一下,说白了就是用数组AR这个工具把它输出来给同学们看一眼。
05:10
对,看一眼,然后共多少条边,我们也写上。共多少条边呢?加上这个AG。对,A级。EDG。把这个拿过来。点认识A,如果没有什么问题,应该是12条边,我们来试一下。在哪里设,是不是在这就可以了,克鲁斯卡K点克鲁斯卡没有问题吧,同学们,我们运行一下,我们发现呢,的确如此。是不是一共12条边,好的,我们接着继续往下编写我们的代码,嗯,那下面应该怎么做了呢?同学们就要根据我们原先这个思路来玩了。哎,首先排序是不是要排序按。
06:00
按什么呢?按照按照边的全值,边的全值大小进行排序,那排序我们是已经写好这个方法了,我们写的是从小到大。是这样子吗?同学们从小到大,那这个很简单,叫short h。把它放进去就可以了。那排完了过后呢,同学们相信当这样一排完过后,我们这个A级子这一个数组呢,它就是从小到大进行排序的,这个我就不去测试了,接着我们开始便利了,便利什么呀。便利我们这个一日。这个数组。是不是这样子的呀,数组,然后就按照我们原先这个算法的思路来玩了,算法是不是怎样子的呢?来同学们看一下算法是不是。思路。按照刚才。刚才这样将边添加到我们最小生成数,同时要判断回路,是这个思路吧?
07:07
将边添加到最小生成数中,使判断还需要判断是否构成的回落,判断是否构成回路,什么构成回路?就是你这个边的两点是否构成回路了,判断加准备加入的边这样写啊,准备。准备加入的边是否构成回落。如果没有,朱婷如果没有,就。就加入到哪里呢?是不是加入到我们这个结构数组里面去,是这样子的吧,如果如果没有构成回路就加入,否则就不要再加了,否则就变下一个,否则不能加入,否则不能加入。就是你现在已经构成回路,就不要加了,那便利了,For循环按T。一共有12条边,我们每一条边都要看一下,是不是需要加入,是不是就是我们边的数量I加加,这个能看懂吗?同学们。
08:04
便利了啊,那你便利的时候你应该怎么办?首先第一步获取到获取到did did条。条第条注意听I条边的。边的这个第一个顶点。其实你可以理解成就是它的一个起点,你你你理解吧,要提这个很好很好写,那就写个P,等于get po,是不是这个方法就有用了呀,怎么写呢,E。Age。轴I点大是不是这个点是不是我们还要获取到第条边的第二个顶点,因为它它有两条两个顶点嘛,一条边有两个顶点,所以说它的第二个顶点,这个顶点,顶点呢,你可以认为是它的这个这个当前这个边的一终点,但你不写也行哈,你可以理解成是它的一个就一个边嘛,肯定是AB,那你可能认为A是起点,B是终点,虽然它是它是无像的,但是你在写的时候肯定还是一个顺序嘛,对吧,那我这这样写吧,第一个顶点和第二个顶点也可以好吧。
09:19
那这个就是P2了,等于get po,然后。H,然后呢,I点什么呢N。这个大家看懂了没有,好,这个看懂了以后,我我这一条边的两个顶点我拿到了,是不是就可以通过。就要去获取你这两个顶点对应的终点是不是已经在我们的最小生成数里面去了,能理解吧?好,下面又接着写获取,获取P这个顶点。这个。PE这个顶,当然它返回的是个下标,这个刚才已经讲过了,P这个顶点,它在注意听这句话,在我们已有的最小生成数中。
10:09
对的,这个终点是是哪一个。终点是哪一个?因为因为你要准备加盟,看看两个中点是不是相同的嘛,对吧,那就特M等于什么呢?好,那个方法已经写好了,Get a。那么这个数组N的刚才我们已经已经六出来了,它所以说它是逐步加进去的,明白吧,好,那现在。那这个I应该写成几呢?写成写成P1。这个能理解不好,紧接着呢,我们要获获取P2这个顶点在已有最小生成数,为什么叫已有呢?就说你这个最小生成数是逐步形成的,所以说它是有了过后你先加了一条边,再加第二条边码,所以说它是逐步生成的,因此我这用的话是已有。或者叫当前这个最小生成数,OK,那N等于各位同学,Get,仍然是N,这个地方仍然是NN好,但是这个后面这个应该写成P2了。
11:11
这个同学们能理解吧,好,现在呢,我们判断。判断是否构成回落。是否,是否这里这条边会加入,会构成回路,是否构成回路。构成回路就是看这个M和N是否相等,是不是我们在前面讲这个分析图的时候也是这样子的,你看为什么我们在第四步不能把这个CE加进去呢?因为CC在已有最小生成数的顶点是fe,在已有最小生成数的顶点也是F,因此不能加入,是这意思吧。所以说这个地方我们要。用这样一个判断,如果M它等于N,那就更回路了,那如果不等于,我们才能加进去,明白吧,就说M不等于N,说明不构成回路,因为它两个顶点就准备加入这个边的两个顶点,它并没有指向同一个终点,就说这是没有构成。
12:12
构成回忆录能理解不?其实并不是很难,对不对,呃,那么这个时候我就如果没有构成回路,好的,那我就干什么呢?同学们,我就先写这句话,大家看这句话是干什么啊,这句话是设置,设置M。MM,但是是这个点了,M在在已有。已有最小生成数的中的终点。呃,因为也就是说你现在你发现这两个点呢,并不构成回路,是不是你要把它加进去,加准备要加到我们这一个。呃,Results这个数组中了,但是你在加入之前是不是要要先把这个就是记录最小生成数各个顶点的终点的这个数组先更新一下。
13:05
是不是?也也就是说,如果这样写的话呢,你可以理解成打个比方,我们第一,我们第一次是不是把哪条边加进去,我我给他简简单解释一下,你第一次是把EF加进去的。也就是说,你第一次在没有处理的时候,这EF。你把这两个加进去,相当于这个数组变成什么样子了呢?这个数组相当于是相当于是这样子的啊,零我我我估计啊,应该是什么样子的就是。你原先是零几个零,12个零对不对,是不是12个零,我复制一下,因为你刚刚做成这个NN值时,其实没有加东西嘛,所以它应该是12条边,就是12个零。六。好,大概是这样子的。当你把这个动作做完以后,哪个会变化呢?因为你第一次取出来的时候,你第一次取的是是EE这个。E的话,E的话这个P1。
14:01
P1是几呢?E它这个P应该是AB应该是几,我看啊。应该是四对不对,零就是我们E是第五个点嘛,呃,Abcde,那这个就应该等于是四,而我们这个F它对应的这个下标应该是五。我们先看一个好的,当当你这个盖的嗯子的时候,同学们,同学们注意听,当你这样去处理过你盖的嗯嗯。如果你传一个P4进去,你们知道它的顶点是哪一个吗?按照我们这个写法,按照我们这个写法,大家可以看到,我们得到的它的这个终点是,如果不等于零,我们就去返回,如果等于零会怎么样呢?如果等于零,就直接返回,它自己下标,就好像说如果你还没有加入进去之前,你的顶点就认为是你自己。
15:02
能理解吧,呃,我不知道大家听懂了没有,就你还没加入的时候呢,我就认为是自己,也就是说这个时候针对他来说,这个M其实就等于四。就你还没加进,加到这个最小生成数的时候呢,我们认为这个人的顶点就是他相当于是他自己那种感觉对不对,原上来就就等于零嘛,那现在这个N是几几呢,也等于五好,当我这样做完了以后,这个时候会导致我们这个N值这个速度哪个变化呢?就是。第四一个。下标为四会变下标为四,其实第五个数就会将这个零制成几呢?制成五。大,大概明白什么意思了吧?哦,别人一看说,哦,D下标为四的,你就这样理解下标为四的这个顶点,它在最小生成数里面对应的终点是五极,什么意思呢?即E的中点。
16:00
E的这个终点。是谁呢?是F。4F。当然有同学说了,说老师那这个不对啊,你应该把这个F也加进去啊,相当于说这个地方也应该是五呀,对的,如果你有这个想法,说明你还是在动脑筋的。因为你你想嘛,你你第下边为五的其实才是F嘛,这样一查哦,就是这个,但是你不要忘了,你不要忘了我们写法,其实这个地方你不用去记自己,为什么呢?因为我在这个地方有一个。有一个算法,你们有没有发现,当它不等于零的时候,我们才去,我如果它不等于零,我们就走,这个你看假设我们要取F的这个顶点,它上来过后是不是就是等于零?是不是等于零,它上来过后,如果是对F取。在下一次我们再对F取,你会发现F还是取到五的,为什么呢?你们可以看一下这个算法。
17:01
他上来过后再去取F。再去取我们看一下啊,比如说这次我要取的这个I是等于五的,而现在这个数组呢。第一次这个更新完了,这个数组其实已经变成了这样一个数组。变成怎样一个数组,变成这样一个速度,我问大家,你把I等于五传进来,再把数组传进来,请问它取出来的这个顶点是谁呀?它是不是先YI5等不等于零,你现在等于零吗?它是等于零的,如果它等于零。如果它等于零的话。他会怎么办?因为它不等于零,它才会进来,如果它等于零,是不是他把自己自己返回去了,所以它返回的还是自己,明白了吧,那下一次这个四,比如说你取的这个I要取四就不一样了,I要取四,四一进来,它判断自己的下边为五,所以它就直接进到Y循环,把这个I制成了五,再返回五,所以这样子就一步到位了,因此同学们,你们不用去考虑说,诶,为什么没有这句话。
18:07
为什么没有写这句话就是N等于N,没有必要写。没有必要写,因为你你这个刚才那个算法已经可以搞定这个事了,明白了吧,好这这句话其实是不写的,不写的,然后results。OK,那现在我们相当于已有一条边已经加进去了。这个能理解吗?就是有一条边入选了,入选了哪条边呢?就是我们当前I这条边入选了,为什么是I呢?因为你I等于零的,也就是说这时有一条。有有有有条边有E。一。条边加入到这个results数组。Results数据理解吗?哼,有点不好理解是吧,其实也不难啊,同学们,就我这讲的是有点啰嗦,其实道理其实挺挺简单的,待会呢,我们可以d bug这个代码就写完了,也就是说到此为止,其实我们这个最小生成书就已经写完了,同学们。
19:08
就这么一点东西,一个复循环完事了。但是你前面有很多准备工作,就代码已经写完了,你看排序,排序完了过后,先得从这个我们这个A级里面顶点拿,拿出这个P1和P2看看,呃,得到这个你你这个顶点。这个A里面得到这准备加入的这条边的两个顶点,然后看这两个顶点是不是构成回路,如果不构成回路加进去,如果构成回路M相等怎么办呢?就不要加了,直接再看下一个。一下一个边看看能不能加进去,是不是就写完了,写完过后我们得看一下代码对不对啊,所以现在我们我们写个统计方法啊统计。并打印,打印哪一个呢?打印我们这个最小生成数,最小生成数就可以了,那最小生成数同学们刚才已经知道,最终它是放在我们的这个results这个数组中的,是不是,其实你只要把这个results数组打出来就可以了,但是这个results数组呢,它仅仅是记录了记录这个这个边的对象,你到时候输出来不好看。所以说呢,我们。
20:17
把它稍微处理一下,大家看啊,我说白了就是输出什么呢?说白了就是输出我们这个result数组。就完事了。理解这个意思吧,好,我们我们输一下吧,干脆。好,我们写一下system,走一个,我们写个最小生成,生成数V。好加一个,我们看看AA。OK,好,同学们注意听点two string,然后把results放进去。是不是就可以了呀,同学们好,现在代码呢就写完,我们可以先看看到底OK不OK,运行一把。
21:00
运一把。好,同学们看图的整个这个集合,这样最后生成这个数,我们看一共有几条边。EF。二入选CD,三入选。第一是入选。下一个是不是就是BF这条边入选了。BF这条面入选七。好,这个干脆这样走,我这这不好看。我要不要不我稍微格式化一下好不好,同学们,我格式化一下,这个看起来太难受了,我格式化一下。怎么格式呢,这个star咱们就干脆换成这样子,大家看行不行。换成这样子的好吗?换成这个。这边摁的。嗯,Star,然后这个N咱就不要了,好吧,这样这样看行不行,好看一点,Star输出一个字符逗号,End输出一个字符。呃,然后这边呢,咱们。
22:01
咱们把这个改成等于就可以了,这样是不是好看一点啊同学们。看起来舒服一点嘛,好,我再运行一下,看一下效果。好,可以看到它原始是AB这条边,AF这条边,最后这个结果看出来EFCD。好,De。BF。BFBF完了是EG8这条边,然后是AB这条边,最后还有一些零的,这个呢,可以不去管它了,因为有些边没有入选嘛,你一共有12条边。你12条边,你真正入选的到我们这个数组的呢,其实只有六条边对吧,所以说你在这输出的时候,你也可以判断一下,加一个判断,因为我这嗯,我这个地方是直接把这个数组是说出来的,所以有有点笨,那这样子我再重新。重新处理一下吧,好吧,稍微费点事,没事零。
23:00
I因为你现在实际上加进去的只有index这个,这么多条边,你没有必要把它全部输出,是这样子吧,同学们,所以说I呢,咱们就小于index就可以了,因为你一共12条边,你其实是选了六条,六条边进来嘛。是不是这样子好,我把这个稍微的整理一下就好看了好吗?给同学们再稍微的整理一下。好,那这块我就不这样很笨的这样输出了,就这样输出system干啥呢,咱们这个results。对不对,把这个I放这就可以了,这样看起来就very。Easy,好,再看一下。好,这样看起来清清楚一点的好,同学们看你原先集合有12条边,我就不一个个去除了,一共一肯定是12条,现在经过我的一个处理呢,我们最小生成数是这么几条边是。呃,这样比我们可以看看跟我们原先这个图是否一样,我们把这个结果打开看一下。
24:02
对对照一下啊,各位朋友对照一下。好,我把这个呢,还占卜到这来哈,占卜到这来,我这边挪一下大家大家比较一下就可以了好吗。就放这儿。比较一下对不对,我们验一下。念一下来。跟着老师验一验啊验一下。呃,EF。顺序也很重要,CD CD OK de de没问题,DFDF没问题,Egg没问题,B没问题,那总共呢,一共是全值36,这边加起来也36,好,同学们,那关于我们这一个用克鲁斯卡尔算法来生成我们最小,最得到我们最小生成数的代码就写完了。大家看是否?呃,能够理解好吧,也不是特别难,对不对,好,那关于代码我们就聊到这里。
我来说两句