00:00
同学们,我们把刚才分析的这一个图解思路,就是普里姆算法解决修路问题的这个思路,我们用代码给大家实现一把,打开我们的这个eclipse。我们新建一个包。对,新建一个包,那这个包呢,我们就叫P。Printmp算法,那现在呢,我们写上一个类,好吧,写个类,这个类呢,我们就叫prime。Prime。All。高瑞。对吧,普里姆算法。把这个勾上,那下面呢,我们就开始来编写教程代码,那大家想你为了来完成这一个修路问题,你是不是首先先把这个图创建起来,我们用临界矩阵把这一个图创建起来,所以说我们先来把图搞定。那首先呢,我们怎么做这个事呢?来吧。
01:02
首先我先建一个图。对,叫M。那在这个图里边我们需要有哪些属性呢?我们先定一个vertex。这个呢,我们先定义一个属性,叫做表示节点图的节点个数。这个没问题,再来一个叉,因为待会儿呢,我们要用abcd来表示村庄,所以说我用这个char数组来保存我们的数据,叫data。对吧,这个呢,保存节点的数据,存放节点数据没问题吧。很好,那紧接着我们是不是还要有一个临接矩阵来表示它的边,我们就叫which。全职嘛,位置。存放边。存放边这个呢,就是我们的临街矩阵。
02:05
临街。对不对,临街。零。临街。临接矩阵,OK,那到时候我们写一个构造构造构造器,那么写个构造器很简单,那么G。然后你给我传一个什么呢?各位你把这一个节点的个数传给我就可以了,就说你有几个节点,那么我就可以来初始化我们这一个存放节点的数据,是不是这也很简单,我们就取个名字叫加个S吧。加个S好吧,这边我们也加个S代表节点的个数,那就z.vertex。然后呢,写上你传进来的这个数据,紧接着我们就可以初始化了,Data等于六,一个char数组。
03:01
对吧,恰是组它有多少个数据呢,就vertex。放进去就行,紧接着是不是这个位。Wait呢,它是一个二维数组,我们要进行一个初始化,是不是六一个int走那几行几列呢?显然跟你传进来的这个节点一样,你节点有几个,我们就是几行几列。各到七就写完了,写完过后我们下面呢。就先呃,建建建一个什么呢,因为待会儿我们要创建的是最小最小数,所以说我这取个名字就叫创建最小生成数。生成树好,这个生成树就是待会儿我们对应的这个路了,就是村庄啊,有点类似于我们这个村庄的土村庄。村庄的这个图,好,现在呢,我们写一个,我们取个名字叫mini tree,没问题吧,Mini最小生成树嘛,那这个。
04:03
那里面有什么方法呢?首先我们要创建。创建图的临接临接矩阵,也就也就是说你要有这个图的临接矩阵,我们才能够去得到一个最小生成数,对不对,你要把这个传给我,那就写public,注,听VO,我们就取一个叫create create create什么呢?我们的graph。没问题吧,那你给我传进来,这个给我传进来就可以了,把这个图对应的对象传过来graph,然后呢,你要告诉我你有多少个顶点vertex s。另外呢,你还要把数据给我,是不是一个数组啊,这肯定是个数组。对吧,然后还有一个什么东西要给我呀,要把这一个临接矩阵传给我,VGT位置是一个二维数组,是一个二维数组,我写到前面吧。
05:03
对不对,好。好的,那我拿到这些数据过后,我这做一个注释,同学们,这个就是你传进来的这个图对象。图对象没问题吧,图对象下面这个代表。图对应的顶点的顶点个数也没问题,下面这是图的各个顶点顶。顶点的值没问题吧?下面就是图的临街矩阵。临街矩阵。OK,好的,那有了这些信息过后呢,下面我们就比较热了,我先定一个I,定一个节干什么呢?我要完成一个初始化的工作,我要完成一个初始化工作,那现在开始写for循环。I'k。In ti等于零,I小于节点的顶点的个数I加加没问题吧?For循环氨替节。
06:09
节等于什么呢?节也等于零,呃,我们看看解等于零,那这个地方没有必要哈,因为你来一个这个就是顶点的嘛,就是在便利顶点。如果是顶点的话呢,来一个就把数据给到他就可以了,是这样子吧,来一个就给到他。好,那现在呢,我们这样写,看看大家能不能理解。它里边不是有data吗?好,然后data的第二个就应该是我传进来的这个data数据对应的I这个元素。是吧,好,这个比较简单,比较简单,这个地方不能再去定义了,不好意思。啊,你不能写两边对吧,不能写两边这个地方应该是逗号好的。那这个就是把什么呢?把我这传进来的顶点的值传给我们这个图里面的data这个。
07:02
就行了,那紧接着我们for循环int解,呃,这个节也不要解,等于什么呢?零解小于来走一个ver t。然后结加加,这要干什么呢?同学们,是不是在这种情况下,我们就可以把它的临接矩阵给进行初始化,临接矩阵它的第一个下标为I,第二个为截值从哪里来呢?就从你传的这一个二维数组我取出来就可以了,也是I减。好,这就写完了,那写完过后呢,为了方便这个mini tree呢,我们再提供一个显示显示图的一个方法,你把这个gra给我,我就把这个图输出来给你看,就这么简单,好吧,我写一个public void show grab。你把什么给我呢?你把这个图对象给我,我就给你输出这个图对应的矩阵,显示图的临接临接矩阵,像这样就好。
08:10
理解了,那我现在写一个方法for循环,按T。对。I等于你你现在有,你想在你现在想想啊,这个图给我们了,其实我们要把他的这个vertex拿出来,就知道有几个顶点了,是不是那I小于G,它的顶点的个数没问题吧,I加加,I加加完了过后呢,我在这就可以直接进行一个输出了。是不是,诶这样我们干脆简单一点,用破循环增强来编利,它每从这个遍历出来就是一个连接嘛,就相当于是个连接一条边怎么取呢。点它的weight,这样就比较简单,那这个时候我们直接用一个。
09:01
这个工具类to string,把神放去,把link放进去就可以了,也就是这个时候呢,就会把临接矩阵进行一个输出,好,同学们写完了过后我们来玩一把,测试一下。测试。测试看看图,就是我们这个图是否创建成功,是否创建成功。好的。嗯,那首先同学们想,我们是不是先要把顶点的值先。把它定义好,对,那我们六一个char,六一个char数组里面呢,我就放数据了,好吧,有哪些呢?我们有AB这个顶点,有这个顶点有C。有de,有ABCDEABCDEF。F过了就是G。好,同学们可以看到现在我一共有几个顶点呢?1234567正确,好,有了这个数据过后,有了这个数据过后呢,我们就可以把顶点的个数也拿到了vertex。
10:13
Ver它呢,一共有几个顶点,我们通过贝塔点就能算出来。好,现在我们来把这个临街矩阵。连接矩阵的关系使用一个二维数组,二维数组描述下。对不对,以前我们也是这样写的嘛,那这个临界矩阵呢,同学们,我们用一个临界矩阵描述了,那这块我已经有准备了,好吧,我不可能这个呢,就是他一他一共有这么几个关系,我们来看一下是不是样子的。看一下。我这里呢,已经把这个准备好了,主要是为了让我们速度稍微快一点。同学们可以看一下。这边呢是相当于是A。
11:01
BCD。EF。G这列也是ABC。EFG,好,我们简单验一下就可以了,A和A之间我用1万表示,我用一个大于零的数来表示什么呢?来表示他们是不连通的,明白我,我的意思就是让他们圈子很大,因为你的圈子很大,你肯定就不会选这条路吗?明白我意思吧。好,那么A和B之间的。它们的距离为五,A和C之间的距离为,C为为七,A和D之间不连通,就用1万来表示,我用了一个比较大的数据,你可以,当然你可以写的再大一点,A和E之间也是不连通的,A和F之间也不连通,A和G是二,用它的距离为二,其他依此类推,也就是说大家知道我这里呢用1万,用1万表示。
12:00
这个大的数,这个较大的数,大数。大数表示什么呢?表示两个点不连通,哦,不直连,不连通就行了,好吧,大家知道这个意思就可以了,不连通。就行,那有些人喜欢定一个更大的数据,这都无所谓,因为你你不管怎么算他,他不可能到1万嘛,对不对,所以说我整了一个比较大的数,就这意思。好,那有些有些人这样写,你也是可以参考的,有些人他怎么去设计呢?就是他定一个呃,N能最N的最大,就是int一个最大值来放也是可以的,好吧,这点大家自己知道就行了,好这个走完了以后呢,下边我们来做一件什么事情呢?我们来创建。一个m graph的对象。那这个就简单了,我们六一个6mg graph。
13:00
那顶点个数刚才同学们已经知道,我们已经得到了,一共有七个顶点,我生成一个变量,就m graph,拿到这个以后,下面我们干什么呢?我们就创建E。创建一一个一个m mini mini mini tree对象就是最小生成数,这个对象也很简单,6MINI好生成它。生成以后,我们用这个mini tree去创建我们的这一个对应的图,没问题吧,Mini。点。什么呢?Create点,诶啊这写错了,Mini mini点。Create graph,那这个图也传进去,顶点也传,Data也放进去了,Wait也放进去了,好,这时我们来输出看看graph graph。是吧,M graph,那这边我们也可以改个名字叫,这样就更直接了,就是图。
14:02
是不是更直接一点,然后呢,我们就输出。输出我们看看对不对,同学们,嗯,很简单,我调用刚才我们写的这个方法。嗯,这怎么回事?点show gra把这个图传进去,我们运行一下来,朋友们,我们运行,我们看到这个结果呢,我们想的一样哈,就是我们这传进去的一个二维数组长成什么样子,它也也是什么样子,但是注意此时此刻我们这个图里面的vertic data还有V就已经被初始化了。那下面呢,我们重点就是去写这个核心的方法,让他。让他能够得到我们这个最优的就是得到一个最小生成数,下面就是核心的算法。下面就是核心的算法,好,嗯,核心算法呢,我们我们这个下面马上为大家讲解。
我来说两句