00:00
各位我们继续编写,那刚才呢,我们把这个。克鲁斯卡尔的图创建起来,我们接着写其他方法,那同学们可以看到,在我们刚才做这个分析的时候呢,我们知道有一个这样的步骤,就是我们需要对所有的边按照全值进行大小的排序,那你首先得有边。你首先得有边,你才能够进行大小排序对不对,那所以说我们要写一个,嗯。要去定义一个编类是这意思吧,所以说我看啊创建。创建一个类,这个类呢,我们取个名字叫做E。它表示什么呢?哎,它表示它的对象。它的对象实例,实例就是说实例就表示表示一条边。那你想想我们一条边最主要的是什么?同学们,如果没有,呃,没有忘的话,大家知道我们对于一条边来讲呢,它应该有两个顶点,还有一个全值,对不对?就说你你在表示一条边的时候,你得告诉我这条边的两个顶点是什么,以及它们的全值是多大,所以说我在写这个类的时候呢,我应该这么去定义class。
01:22
Data。好的,那我怎么写呢?首先我有一个start。OK,那这边呢,我们叫做边的起点,注意听边的起点。就是它的起点是哪个,然后呢,是不是还有一个边的中点,我们用end。边。边的终点。这个大家能能理解对不对,一个起点,一个终点,注意这个终点指的是不是说不是说他最终的一个终点啊,应该是他的。
02:00
嗯,就是这个意思,同学们,这个终点代表的是,比如说B和F,那么假如我们认为是从B到E这样一个关系,我们写一个B到F这样的一个关系啊,大家知道就可以了,好,边的另一个点吧,边的一个点,边的一个点,这样写边的另外。另外没问题吧,另外一个点。好的。那现在这个写完以后呢,我们是不是还有一个全职啊叫位。这是边的全值,能理解W。GT,没问题,编的全是好,现在呢,我们需要有一个构造器,构造器也把它写上public e。那你在构建一条边的时候,你是不是应该给我传一个start,一个点,还有end这个顶点,然后就是它的全值能理解位置。好,现在我们将其。
03:06
进行一个处理,Star。等于什么呢?等于你传进来的这个star。没问题吧,好,我们再写this.end end写错了。End。等于你传进来N的这个地方是逗号。好的,然后呢,this.weight它的全值等于你传进来的这个全值,好,这是它的构造器就有了,有了构造器过后呢,我们还需要待会呢,我们会输出这个点,因此呢,我们要把它初始化一下,就进行一个显示啊,后面这样子重写,重写to实训方法。便于什么呢?便于输出。便于便于输出这一条边。
04:01
很简单,那就重写一下。重写一下就可以了。好的,那我点一下厨师俊,我把哪个勾上呢?显然这三个应该都要,是不是咱们都把这个三个勾上吧,勾上但是这个格式我们要稍微的调整一下,就是它是从哪条边到哪条边的,我看看end start,它end圈子好可以就用这个形式吧,这是输出。输出这个边的信息。好,那有有了这个e data这个边的类过后呢,下面我们就可以继续往下写了,那同学们跟上我的思路,大家都知道,刚才我们在做这个分析的时候,我们讲过,就是你的边呢,先要要先要是排序对不对?是不是有一个排序的工作呀。是不是有个先要先要按照边的全值进行一个排序,再进行下面的处理,是这样子的吧,好的,那现在呢,首先我们先来写中代码对边。
05:07
对。小这对边。对边。进行排序。排序处理。那这里呢,我我就用我们最传统的方法,用一个冒泡,好吧,我们就一个冒泡来进行排序,很简单的,那现在呢,我们就写这个方法,Private void。NGG这样的吧,Edgh,然后你把什么传给我呢?把这个边的集合传给我就可以了,对,E。E DG ages,然后呢,这边你这个元素本身是什么,我用element表示。就是你这条边是。这个对应的这个,呃,这个长度长度。
06:02
好,下面呢,我们来处理一下这段代码,我们来处理一下这段代码。我看看这个有没有必要要啊,一这个地方没有必要再要,它不要了,直接进直接对我们这个1DATA进行排序,我这里写个注释,这是我们边的集合,那么这个功能是干什么呢功能。他完成的这个功能就是对边进行排序,而且呢,这里面大家刚才也看到了,我们用的是冒泡,我们待会用冒泡来排,好吧,同学们的代码就可以继续写了,冒泡排序吧,应该对我们来说一点都不陌生,两个不循环就考可以搞定I小于。Engines。A点嫩。减去一个一,这里我就不复习了,好吧,就只用冒泡for循环NT节节等于几呢?零是不是解小于A级时。
07:03
Ages。点什么呀,同学们,N是不是减去一个一再减去一个I还记得吧,然后节加加。很轻松的啊,这块冒泡如果还没有听明白的,自己再去看看冒泡排序,那现在呢,判断如果什么。这个全职哪一个呢,就是节。节对应的这个全值,它大于了,大于了它后面这一个。后面这一个A级对应的全值,那么这时呢,我们就进行一个交换。是不是这面要交换呀,同学们要交换,那交换的时候呢,也非常简单,我们定一个e data没问题吧,我写个零时的变量,然后先把我们这个节对应的边。
08:02
这个下边对应的边保存起来。对,保存起来E看看啊不对,是这样子写EA,然后呢,我们再把。什么呀,进行交换嘛,那肯定就是结。让这个1H日节加一这个只付给我们这个节是这样子对吧,紧接着呢,我们。Ages。Edges的哪一个呢?节加一,它就应该等于temp。这个这条这个变量指向的边好了,这样整完了以后,同学们这个处理完了过后,我们这个排序也就自然的完成了。排序完成,那排序完成过后呢,我们还要紧接着写别的方法,下面呢,我们还有一些方法需要写才能去写克鲁斯卡尔算法,我们下面再写一个什么方法呢,同学们。我们写编写一个方法。我先把这个洗出来,我们再做注释,好吧,Part private。
09:04
Private get position position什么呢?你把一个顶点给我,我返回这个顶点对应的下标,我把这个在现在可以做注释了。哎,这个就是你传入的什么呢?就是顶点,顶点的这个值,也就是说你这个顶点是A呀还是B呀,还是C,我把对应的下标返回给你,明白这意思吧,返回什么呢?注意听返回。我这写清楚吧,把顶点的比如对吧,我们写个比如让大家一下就清楚,比如A。B单这样,你把这个顶点值给我,那返回是什么呢?返回的是CH这个顶点它对应的什么呀,下标,那如果找不到,找不到也就你你给我瞎穿一个顶点。
10:01
找不到我们换回什么呢?负一就完事了。哎,那代码就很简单,那么我们来处理一下一个for循环嘛,N tii等于零,I小于谁呀,同学们肯定是从这个verex这个数组里面去找吗?对不对?我哀加加,我哀加加,各位同学请看代码,如果这个verex。这个I它就等于了你传建CH说明什么?找到是不是说明找到找到,如果找到那就不用犹豫,直接把这个I返回,如果我们整个for循环结束过后还没有返回,说明找不到,找不到找。找不到,如果找不到返回,返回负一即可,Return负一,那么完好,这个方法就写完了,紧接着呢,我们还有一些重要的方法,还要去写哪些方法来跟上我的思路,跟上我的思路,下面呢,我们还有一个特别重要方法,我先把方法写出来,好返回什么呢?E。
11:06
Data。这个方法是要做什么?对,Get。以ages。这句话要干什么事情呢?同学们,听我说get edge这个方法,我是要做这样一件事情,我先把我要干什么事给各位朋友们说一下功能啊。这个方法实际上是这样子的,获取图。中途中的边。图中的边放到哪里去呢?放到。E。德塔这个数组中。二数组中,然后后面后面我们要干什么呢?后面我们需要需要遍历该数组。遍历该数组。这个同学们可能现在还不明白这什么意思,就说我们不是有很多边了吗?
12:05
大家知道就是我们我们我们整个这个倒行构建的时候,同学们也也已经看出来了,在运行的时候,我们我们拿这个也也可以看我们将来会有很多边。这个。非零的,非非零的,而且不是应付的,就是一条边,那这条边你最终是不是要放到一个数组里面去,我们才能变利啊,诶,这个就是干这件事情的,后面我们需要便利,就这个事,那么它是通过什么来获取的呢?我再接着写注释,是通过matrix,挺简单的啊,同学们通过这个ma matrix临接矩阵来得到。临街。连接啊,这个单词临接矩阵来获取。来获取,OK,非常的简单,存包的形式是这样子的,我先写下将来我们这个E。
13:00
Data,它这个形式大概是这样子,我先简单的给同学们写一下啊,比如说这是个集合,里面我们发的是什么呢?哦,有A有B,说假设我们有一条边是AB,它的全值是多少呢?12。OK,再比如说同学们看我们这个图也能看得出来是不是,同学们有没有发现BF就是你们看到的BF这条边,它的一个点是B,一个点是F,是不是全值为七,如果这个也存进去的话呢,它这边就应该是这样存放这一条边的,注意听是B。F和七,当然还有很多其他的,你有多少边,我们到时就可以获取到。一共有多少条边,一共有多少条边呢?其实这个时候你在没有真正去处理的时候,它的边应该是这里所有的条。有多少条就是多少条。明白这意思吧,就是他最初的这条边这么多,边有哪些,那我开始写了int,我先写一个,说第一个index待会有用,那么我们先把这个创建起来。
14:12
New。你有一个什么呀E。E塔那多不是这个啊,OK。写到这吧,有一个这样的速度,那它有多大呢?同学们,显然是我们这个边的条数,还记不记得同学们我们在初始,我们在初始化的时候,哦,这个地方是什么意思,我们还没有去定义是吧?诶,那这个地方我们还少一个变量E。A级A级四。E e s edge,也就是说到时间我们将把会把所有的边放在这个集合里面去,那有多少条边呢?你在刚才的这个构造构造器的时候,是不是已经把边的条数已经统计出来了,统计边的条数?
15:07
调数能理解哈,就是现在我有多少里边我就创建这么大的一个数组,准备存放边,就是存放形式是这样子的,明白他现在我开始进行一个负循环了,我要负循环谁呢?要负循环我们这个临接矩阵。这个应该很好理解对不对?Ver text I加加不着急啊,同学们,这个题有些算法呢,是比较麻烦一点的,但是也不是说很难很难好吧。它这个节的时候,我在便利的时候,我就这样变利了,我就不用自己跟自己变利,没有意义吗?比如说你临进来过后,还是你没有意义,所以说我这I加一,明白我意思吧,我就I加一好也小于什么呢?Where text.ms还是一样的。解加加能理解好同学们。
16:01
写完写完,紧紧接着我们就判断,如果matrix注意听matrix,它对应的这个值干什么呢?它不等于in。不等于应付。OK,那么我们就把这条边加进去,那也就是说如果你是零的话呢,我们相当于也把它是不是相当于也进行了一个处理,因为你这会跳过你自己跟自己呢,呃,不就不再去做这个比较了,那现在我们就可以把它放进去了诶。Age是什么呢?我们的index。哎,我进行一个加一加,加等于六出这条边1H,当然我们可以看一下它的情况是什么样子的,首先这个star就应该从我们这个。Vertex。也就是我们顶点集合里面来取是这样子吧,End是不是下面这个,因为我取两点嘛,我不能说自己我我我我取的是两点嘛,对不对,所以说一个是I,一个就是截了呀。
17:07
我电力整个数组嘛,肯定是这边就是解没问题,再把这个值放进去,全值是多大呢?朋友们matrix来。这边是结就完事了。经过这一个处理,我们就把这个拿到,拿到过后呢,我们。Return我们这一个创建好的HS。那同学我们可以试一下,看看他到底长什么样子,好吧,我们先简单测一下行不行?没问题吧,同学们,我测一下,给同学们看一看。好,我们来简单的测测试一下,点get ages。然后呢,我这儿呢,也不返回,我就临时的给同学们看一看,它返回的这一个边的数组,就是所有边的数长什么样子,给同学们看一下,我运行之。哦,我这边是不是没有打印呢。
18:02
这面应该是打印了呀,Get age。钙age。我看看掉了没有。返回了吧。Get。Age get age应该返回了,返回了过后ver metricx,好,这个应该是。可以的吧。哦,同学们,这个地方matrix。不等于这个就返回去,诶为什么没有输出呢?我们来看一下问题出在哪里。我把这个。写个叉叉,表示我这有一个输出的动作。好,这方这样输没有办法,他这样输呢,它直接输的这个地址,那这个地方我们要看的话啊,同学们,因为它返回的是一个数组嘛,所以说我们要看的话得这样看了。这样看才行,你看呢。这样看好吧,我们用个A。这大家能理解吧,点to string。
19:01
诶把你返回这个数组呢,我们把它转一下,转一下再来执行。好,这样大家看的就比较清晰了,你看全是12 AF全是16,但是这个时候没有排序哦,同学们你看这边是AG是14。对吧,诶你看这边都把它全部记录下来了。是不是全部记录下来了,后面还有很多空,还有很多空,很多空是什么造成的呢?我们来看一下,我们看看现在我们一共有多少条边,这个排不好数,对不对。还有这么多。那么后面还有一些空,我们来看空的原因是怎么导致的?好的,同学们。我们把这儿打开。Get。诶,我们get来看看。Get。Edge edge这地方应该是,我看我是怎么判断的,它的变数只要不等于。
20:03
非空我们就加进去,那也就是说在统计这个边的时候呢,如果是零,其实我们是统计进去了是吧,如果是零的话,我们是统计进去的,而在这个地方处理的话,处理的时候呢,如果他非如果不是这个的话呢,就放进去,但是因为我们在进行这个处理的时候,自己不跟自己进行判断,因为你I进来是零,这边是I加一,他自己不不处理判断的话,这这就跳过去了。就跳过去了,那这样子也是没有问题的,这样做也是没有问题的,好吧,也就说我们这统计的结果就是我们看到的这样一个输出情况。看到输出情况好,我们接着继续往下做。看一下。嗯,这个地方我。我们要不这样处理一下啊,同学们看,刚才我们在运行这个边的时候,这个边的时候呢,大家可以看到这后面还有一堆这个空,这个空呢是就是因为我们在统,原先统计这个边的时候,把它自身很它自己那个林液统进去了,统计进去了,那干脆我们这样处理一下,不要不要统计自己这条边了,那怎么办呢?怎么办呢?咱们这样处理在这个地方呢,咱们这写个I加一就可以了,这样就看起来更清晰一些,就是我们就认为你自己跟自己这个就没有必要再去连了,把它排排出去就I加一,好,我们再来运行一下,这样看起来就更好一些吧,可以看到同学们看现在这样子,一处理过后呢,就把自己跟自己连的。
21:40
那个那那条那那条所谓的边就排排掉了,明白我的意思吧。你看,现在看起来就更清晰一点,一共有多少边,待会我们再看。
我来说两句