00:00
OK啊,同学们,我们把刚才的克鲁斯卡尔算法用代码给各位朋友实现一下。具体的要求呢,就跟刚才我们的提出的要求一样,就是完成这一个公交站问题,问题的解法对,就是说ABCDEFG,对吧,我们来找出它的最小生成数,就怎么连接。是OK的,那如果不出什么问题的话呢,我们整个这个结果就应该是这样一个结果,怎样一个结果呀。最后的结果就应该是选择这六条边,好吧,我们就以这个就以这个案例来解决。好的,那现在呢,老师用代码给大家走一遍,打开我们的eclipse。OK,新建一个包包。好吧,我们新建一个包。这个包呢,我们取个名字就叫克鲁斯卡耶。就叫克鲁斯卡尔。克鲁斯卡尔。这个英文词我就不去记它了,直接拿过来用一下好吧。
01:03
出来一下。点新建一个package点儿。OK。把这个K呢,咱小写一把。现在在这里我们新建一个类,跟上我的思路,新建一个类,取个名字叫克鲁斯卡尔的案例case OK。把主方法给各位同学勾上,那下面呢,我们就来写吧。根据我们前面的一个分析,是不是首先我们要把这一个图给构建起来。是不是首先要把这个图给构建起来,这些顶点这些图,而我们图呢,一般会使用临接矩阵来存储,是不是,所以说我们先把图搞定。那首先我们在这一个克鲁斯卡case里面,我们新建这么一些新新建这么一些成员变量,或叫成员属性走一个private in edge。Number。
02:01
注意听,这是干什么呢?这是记录边的。OK,边的个数,因为待会儿呢,我们有多少条边,我们是需要知道的,所以用age number来表示,那下面呢,我们有个差。这面写什么呢?Ver tax,知道什么意思吧,Ver tax,这是我们的顶点。集合也顶点数组对不对顶点的一个数组。数组,那也就是说我们将来有七个顶点会存放在这个叉中,没问题吧,紧接着我们还需要一个什么临接矩阵,临接矩阵呢,我用。一个二维数组来表示这些,前面已经说过了,Matrix matrix。别写错啊,Matrix,这是什么呢?临街矩阵。没问题,同学们好,这些三个最重要的拿到了,我们是不是还需要有一个表示两条边不能连通的这种最大值,也就是说大家看B和G,它就不连通。
03:05
大家有没有发现B和G不连通,那么在不连通的情况下呢?我们原先用的是像1万这种比较大的数据来表示,这次呢,我们用另外一种方式,就是用我们integr的最大值来表示它不可连通,最近这句话我写一个,大家看一下就明白了,Static。到final final什么玩意呢?OK int INF,对,然后呢,我写一个J这样一个变量,大家看能不能看懂integ.max。Value,也就是说我写一句话使用什么呢?使用in。In,这一个变这个量,Finalner类型的,Banner类型的来表示什么呢?诶表示两个顶点,OK,两个。两个顶点不能连通,好了,明白这个道理。
04:02
好,那有了这个东西,我们是不是首先应该写出它的这个构造器,我们直接在这里写构造器没问题,跟着我的思路public来。克鲁斯卡尔case。对不对,然后呢,你给我传一个char数组,就是我们所说的ver text,再把什么传给来传给我呢?Int。这个临街矩阵matrix。很简单,是不是?如果你在主方法里面提供了一个顶点的集合,还有一个临界矩阵,那么我就直接把它付给他就可以了。怎么写?来,我们写一下初始化,初始化。初始化什么呢?初始化顶点数。和什么呀,边的个数,边的个数注意听,那怎么写呢?我们这样写V。
05:01
N我用这个表示我有多少个顶点,那这个就很简单了,就用vertex点什么呢?N。是不是就拿到我们一共有多少个顶点没问题吧,同学们,好的,那现在呢,我们初始化一下。其实也可以直接把它付给付给这个付给这个vers或者max,这也是可以的,但是我这里呢,让我这样就直接把它拷贝过来,这种形式好吧,我们把它复制过来。跟上我的思路,那我这写个叫做初始化,初始化什么呢?顶点。那用初始化顶点的话呢,我们首先把这边拿到的这个ver干什么,六一个char OK,六一个char什么呀,V。这什么意思,就是我先把这一个叉给溜一下。
06:00
大小呢,就是一个顶点的个数,大小就是顶点的个数,而且我把这个顶点的个数呢,给到哪里了,给到这一个。Z是vertic这个数组,明白这个大家大家明白,那这个时候做完了过后是不是。这个数组这个vertic里面还没有任何的顶点,是不是我把它拷贝过来就行了,复制一下。OK for循环,For循环怎么写呢?Anti I等于零,I小于ver。点认识没问题吧,I加加,I加加走一个,怎么写呢?Z是点ver,好,这边我们写上I等于我们ver。这个I就可以了。也就是说我把你这传过来,Vertic付给我们这一个属性里面的vertic这个数组,同时把它初始化。当然有些同学老师你这样做不是有点麻烦吗?你也可以这样写呀,你也可以这样写,直接this是点verex等于。
07:06
等于谁呢?Vertis不就完了吗?也可以,就是你要说你这样子一步到位也可以,只是我我是希望什么呢?将来我们传进的这个vertis,你不要在程序里面把它给修改了,当然你也可以这么,如果你只是进行一次克鲁斯卡尔的这种操作呢,你完全可以怎么样啊,就是直接把这个vers付给他,但是我这里写呢,就是我希望我自己的不要跟外面的有关系,就说我我把你传过来vertics进行一个初始化,我这边的改动呢,不影响你给我传进来的这个ver数组和这个magic数组。明白啊,这两种方式都可以,这个我就用的是复制的方式,注意听我用的是复制。哦,复制拷贝OK的方式明白。好,这写完了后呢,下面我们就要初始化编了,初始化编。
08:00
因为你现在已经有了顶点,你初始化这个边是用什么来初始化呢?就用这个matrix,是不是你传进来的这个数组来初化,那我就开始写了this.max等于6INT。那么我们这个边的二维数组应该是多大呢?A就是你这个顶点的个数。将来。决定我们这一个临接矩阵的行和列是不是好,这样做完了以后,我们是不是也要初始化一把,怎么初始化呢?也把这个matrix拷贝到我们自己的。这个matrix矩阵里面去,我用的是拷贝的方式,同学们,下面我们再来写一下好吧,使用的是复制。复制OK,复制拷贝,拷贝的方式好的,那我们这个地方需要一个for循环,两层for循环对不对?I小于什么呢?为N。
09:03
对,I加加。I加加,然后我们紧接着解等于零,没问题吧,解等于零,那解小于VN。对的结,加加。很简单是不是,那现在我们就把这个值付给他不就完了吗?Ver,呃,不是vertexs了,现在是matrix,然后I。解这边等于多少呢?OK,直接把值赋给它就可以,就matrix里面的I解这就复制过来了,这样我在里面对vertexs的改变和vertexs的改变呢,不影响你外面传进来的。这两个数组了,是这样子的吧,我说了啊,两种方式都可以,只是我这里用的是复制拷贝的方式,好初始化编完了过后,是不是我们要统计一下这个边呢?同学们,我们统计边就是看看我们到底有多少条边呢,因为你这个时候只有这个满足条件的才才代表这个有变,好下面呢,我们就来。
10:07
统计一下这个边有多少条,我就开始写了,大家看一下,M ti0i小于VN。对不对,I加加。然后再来一个for循环,Ant解,解等于零,解小于V,没有问题吧,解加加。其加加完了过后呢,我们做一个判断,如果你这个matrix的这个元素的值,它不等于什么呀,INF说明什么问题。它如果不等于的话,就代表什么呢?诶就代表你这条边是有效的,这个能理解吧,因为刚才我们讲过,我们如果。两条边不能连通,我们用的是NF来进行这个表示的。这定义定义了这么一个来表示它的最大值,那如果它不等于NF,那说明这条边是有效的,于是乎我就把这个边的数量加加。
11:08
满地吧。好,同学们,到此为止,我们这一个图的vertexx和max就初始化完毕了,能理解,那么现在呢,我们可以进行一个测试,测试的话呢,我们就打印一下,打印什么呢?打印我们的临街矩阵。临界矩阵,这个能理解不负循环氨T。哎,我们写一个方法吧,Public。我们写一个方法叫public void print。OK print打印,那打印的时候怎么打印呢?非常简单,我们先写一句话提示它就写,就叫临接矩阵为,好吧,临接矩阵为,然后换一行。当然这个时候呢,我们用for循环就可以玩转了,I ti等于零,I小于vertex,就是我们这个顶点的长度,就是我有多少个顶点,I加加。
12:10
对不对,那这个时候呢,再来波循环,Anti解等于零,解小于ver t点一样的道理,我这里就不解释了,各位朋友。那这个时候呢,我们就来就把这个打出来就行了,很简单,System。Out,怎么打呢?我们为了。我们我们这样打就行了,看百分号D打完过后呢,我们来一个制表符,这样有个格式化,是不是,同学们加个F吧。加F,然后这边的值呢,是什么就是什么。就是I和J写到这里,打完了以后,每打一行我们怎么样换行就可以了,因为你这边便利,意思是不是打了一行啊,打完一行我们换行处理。换行。是不是换行处理好同学们,那关于这个最基本的。
13:05
克鲁斯卡尔,我们要存的顶点还有临界矩阵的代码就行了,我们来进行一个简单的测试。首先呢,同学们可以看到,在进行初始化的时候,我们要有顶点这个数组和magic magicx这个矩阵二维数组,那现在老师就不多说,直接写char。Vertex。等于我们按顺序来吧。A是一个顶点,我们一共有几个顶点?各位朋友,我们有七个顶点,是不是同学们ABC?这是DOK。Abcde。F。FG。是不是同学们记OK代码A大写?大写G,那同时是不是还有一个matrix这一个二维数组啊,我们一样把它搞定in。
14:03
那这个时候呢,我们就有点费劲了,你得。你得根据这个图来。构建我们这个临界矩阵太麻烦了,因为这个要写的话,我我得写七,那我就要我要怎么写呢?我有七行七列,我我就要写14 49下,太慢了,这个地方我已经给他准备好了一点,这个初始化的素材,大家看克鲁斯卡尔的临界矩阵呢,其实我已经准备好,我就拿过来用,这个没问题吧,同学们能看懂。应该能看懂吧,你看零。就是零呢,我们就代表他这个是。同一个点零,注意听啊,我这个时候这个概念有一些变化,大家有注意看到,当它是自己跟自己连呢,这是一条对角线,我们是用零来表示的。那如果说它能够连通,比如说A和B,它们之间能够连通距离是12,我就这样表示的,如果他们不能连通,比如说A和C不能连通,我用的是NF。
15:03
用in来表示,他们不可能动,因为INF它是一个很大的值,是不是是integ的ma max value,这样呢,我就在写代码的时候要注意我的这个表示方式,好的,那这个写完了以后,同学们我们就可以来创建,创建一个。克鲁斯卡尔case的对象实例。这个大家能理解吧?对象的实例六,一个克鲁斯卡。那我要传的这两个参数,一个是vertex,一个是matrix,传进去了,传进去以后呢,我生成一个变量。非常简单,是不是我现在已经把它生成,生成过后呢?我们来看看测试一下,看输出一下这个图输出构建的是否正确,那就特别简单,就用克鲁斯卡点print就OK了。
16:00
郭同学,我运行一把。我们运行完了,我们发现这个结果来。应该是对的,你看没有012这个。就是我们应付代表的最大值,那这应该能看出来对不对,但是你们看到这个对的有点不齐,很郁闷,为什么呢?你看这个是这个是第二第一行的第二个数据,这个你看第二第三行的第二个数据,跑这来了,很不好看,就是看起来没有那么对应,怎么办呢?好办,我们在这地方这样处理。在这我们想一个办法,好吧,想一个什么办法呢?同学们,你看我这样写,大家看懂吗?我写个20。D这个20就代表占位,就说你如果不够20呢,那边就把它空出来,这样子再输出,你看这个效果呢,就好看的多,诶你看这样是不是。更直接一点了,但我的20可能稍微多了一点,对不对,我可以把它改成十五八。15这样看起来就清晰更好了,你看诶,这个15应该还可以再减一点,改成十,看看行不行。
17:06
改成十好吧,我们看看十,哎,十有点不行。改成12。12应该就合适了,同学们看,大致能看出来,也就是说你们可以看到此时此刻的情况应该是这个样子的。好,我把我这个。我把我的,诶这边。好,这好出来了,大家看,这是我们的第一行,你看这个看的比较清晰了。对不对,现在就看的比较清晰了,因为咱们有一个数特别大嘛。所以说你看这个,这是第一行第二行第三行第四行第五行第二行好七行。有几列呢?七列一列两列,三列四列,五列,六列七列。这样我们就把这个。矩阵构建好了,我们可以简单看一下对不对。我们来验一个吧。G和BG和E为八。
18:00
记住啊,G和E为八,我们看看是否能够对应上。怎么看?怎么看?G,这是我们的G点。E是这为什么你看啊,从上面看ABCDEFG吗?这个是abcde,好,你们看这确实是八。其他几年连不通用的是一个较大的数来表示的。好的同学们,那关于我们克鲁斯卡尔的第一个构建图的这一部分功能,我们就已经实现了。那下面呢,我们继续来讲解它的算法,我们放在下一个视频。
我来说两句