00:00
一共有多少边,待会我们再看好,这个写完了过后没有完啊,同学们没有完,因为你你把这个拿到过后,你是不是要进行一个排序,我们还没有试,你我们来把这个排下序,看看能否OK。这个是在没有排序之前获取到的,我掉下克鲁斯卡尔的这一个shot。我我怎么去对这个进行一个排序呢?好,我们来看一下,也就是说如果我们要测试这个排序的结果的话呢,我可以这样去看。这是没,这是没有排序的时候未排序。我叫没有排序。没有排序排序。好,那现在如果排完序播,我们再看这个结果是什么样子的,我们可以这样来玩一把,那我就先给大家这样子处理一下,好吧,怎么处理呢。我们看看排序过到底跟没有排序之前的区别是什么。排序后。
01:08
那我就先快速的给各位同学处理一下,我就复制一份,好吧,复制完了过后我怎么进行排序呢?我克鲁斯卡尔。点shot。好,把你这一点返回结果排下去,我再输出,就这意思好吧,当然实际上待会咱们编程的时候,肯定不能这么去干,对不对,好这个地方它有一个。问题哦,这边是没有返回结果的,没有返回结果的好,我想想这个地方应该怎么输出呢?因为排完序过后,他并没有返回,我要做测试的话,如果我想做测试的话,我还得这样处理,那这样子吧,我就稍稍的缓一步,我先把这个先拿到。明白我的意思吧,诶,我先拿到它这个地方得到的边这个集合,这个没问题啊,这个大家应该能看懂,好edge edge,然后我在没有排序之前,我这样输出。
02:13
是不是好,那我再进行一次排序处理,怎么排序呢?克鲁斯卡尔点short ages把这个传进去,传进去过后这个就这个,因为是引用传递,那相当于就排序了,排序过后我们直接输出,怎么输出呢?好的,同学们这边都不要了,直接把这个edges放这就可以了。这个能理解吧,好的,那现在呢,我们这个地方还少了一个括号,处理一下就可以了,我们看看排序前和排序后的区别,排序前。这是排序后没问题吧,同学们运行之,那么运行完了过后我们可以看到。呃,在没有排序之前,你看全值是12,这是16。
03:04
然后这边是14,显然是无序的,排完序过后,我们看看全职为二。全值为三,全值为四,全值为五,全值为六,为七,正确的说排序这个是没有问题的,我就把这个数拿掉了啊,也就说我这个测试完了过后呢,代码没有任何问题,排序这块没有任何问题,那同学们,我们紧接着后面还有一个方法要去编写才能写克鲁斯卡尔方法。好,Get也搞定了,下面我们还要写一个方法,大家跟上我的思路,Private,什么方法呢?Get end。好,这个方法稍微的有点不好理解,我要给他写清楚什么意思呢?我先把参数写进来,然后再解释,好吧,同学们不要着急摁,然后呢,Int I,我说一下这个方法它的作用是什么。
04:05
嗯,首先我们看,我们首先看这个方法的功能,先描述一下它是获取注意听啊获取下标为I的,下标为I的顶点的终点哦,那老师说这个啥意思,有点不理解呀。啊,有点不理解,我给大家解释一下啊,同学们大家还记不记得我们在做这个克鲁斯卡尔算法分析的时候,我曾经讲过一个是要对边岸全子进。排序这个刚才咱们其实已经做完了,还有一个当我们把这个边加到最小生成数的时候,是不是我们要去判断是否回程形成的回路,而判断两个是否形成回路,是要看它们是不是有共同的。这个最大顶点。
05:01
那也就是说,你怎么知道你从这个最从这个排完序的这个边里面取出来了一条边以后,是不是能够加到我们这个最小生成数的一个问题是,你要判断它是否是否是回路,而判断是否是回路,要判断两个点的中点是不是同一个终点,是不是这个道理。大家还记不记得下面我曾经讲过这个事啊?是不是要判断,你看我们在在做这个这个CE的时候,我怎么知道C和E的它它的这个终点都是F呢,是不是我们写一个方法才行呢。你如果不写一个方法,到时间你这个很麻烦的,所以说现在呢,我们就这个方法就是要获取下标为I的顶点的终点,这个是用于什么呢?用于后面判断,判断两个顶点的终点。终点,OK,点是否相同,OK,这个是非常重要的哦,好,那现在呢,我们来写一写这个东西其实特别简单哈,一个while循环,嗯,这个有点不好理解大家。
06:14
稍微的耐点心,好吧,我也慢点稍微讲慢点讲一下,这个有点不好理解,那么I等于N。End。好,然后这边呢,我们就写上这个I,然后这个I。这这个方法其实是不太好理解的,不太好理解,他不太好理解的地方就是因为它这是个动态的功能。它是一个动态功能,所以说所以说这个终点呢,就是哪一个顶点的终点是哪一个,它是动态加入的,我要写到这里啊,就是。怎么表示呢?这个东西还不好说,我这样写吧。我这样,我这样说,就是将来这个end,这个end子它是记录这个end子,它是记录了什么呢。
07:04
哎,这个摁摁这个数组,这个数组就是记录了,记录了各个顶点,各个顶点对应的终点。终点是哪个?是哪个,而且这个N值呢,是在我们便利的过程中逐步形成的,它不是说你先扫描一遍就知道哪个点的顶点是哪,哪个顶点的终点是哪一个了。你打个比方吧,比如说现在我一上来,我一上来我还没一条边还没有加入,一条边还没加入,那我直接问你,请问AB的顶点是哪一个,你能告诉我吗?是不是他还没有吗?只有等到他准备要把这条边加进去的时候,他先去判断这两个顶点,这两个顶点的终点是不是同一个,因此我在这地方说了一句话,就是这个摁这个数组,这个数,这个数组是在便利便利过程,在便利加入。
08:12
嗯,生便利过程中,过程中逐步逐步形成的,他不是一步到位的。哎,他不是一步到位的,就是它加进去过后,他才加到这个我们这个连通图里面以后,他才知道它的顶点是哪一个,明白这意思吧,这个I我就先说一下,这个I表示什么呢?它表示传入的顶点对应的下标。能理解吧,好,返回的是什么呢?返回的也非常简单啊,我先说清楚,大家注意听,它返回的就是下标为I的这个顶点对应的终点。的下标。啊,我这有人听懵了,这你这整整了半天,我说了这个方法,我待会还要回头讲,大家不用特别的着急。
09:07
因为我说了有些东西呢,你一时半会理解不了,是有可能正常的,我说了算法这个玩意儿,不管是普鲁姆算法还是克鲁斯卡尔算法,我们重点是能够理解病人使用就可以了,你要去彻底的说,诶他是为什么,他这个设计,我待会儿可以给你们讲一下,但是。更重要就是理解,那么关于这个方法它是怎么来的,为什么这么写。我一会儿再。讲的过程中还要回头再说啊,一会儿一会儿。我说啊,一会儿回头回头还要回头还要还要来理解,那待会呢,我们通过第bug或者通过什么方式来看,因为我现在怎么讲都都讲不明白啊,怎么讲都,但是你至少要知道这个方法它是很有用的,它的用处是在于它能够去获取你传入的这一个下标为I的这个顶点,它对应的中点的那个下标。
10:09
因为你必须要有这个功能,你才能够完成。你从这个。集合里面挑出来的那个全值最小的那小边是否能够加入到我们最小生成数?OK,好的,那这个N的N值呢,就是它就是存放的记录各个顶点对应的终点是哪一个,OK,而且记得肯定是下标了啊好,嗯,到此为同学们,到此为止,我们克鲁斯卡尔要用的核心的方法其实就已然写完了。就已然写完了,那么我们这这几个方法,我们看看一下写了几个重要的方法啊,一个方法呢,就是排序的,对这个边。这个集合进行一个排序,这是肯定的,还有一个方法就是获取他的一个位置,待会也要用,就是你传一个顶点的值,我告诉你这个顶点的下标是哪一个明白,然后呢,这个呢是能够根据我们的这个matrix临接矩阵来生成我们这一个边的集合。
11:10
那么下面这个get n呢,它是能够去获取呃,下标为I的这个顶点对应的对应的终点,因为这个方法呢,将来会去用于是否判断是否这两个你两个全子最小的这条边是否能够加到我们最小生成数的一个重要的呃方法,好,同学们核心方法写完了,那待会呢,我们就准备去写我们最最后这个方法就是刻录思卡算法。克鲁斯卡尔算法的代码实现,我们放在下一个视频再为大家讲解。
我来说两句