00:00
继续完成我们的代码,根据刚才的分析,大家有没有发现,其实我们这个狄杰斯特纳算法里面最核心的或者说非常重要的一个类是这个类就是记录以经访问顶点集合,以及它这里面的什么呀,它这里面的三个数组以及以及这三个数组是怎么变化的,是不是?所以说呢,我们先把这个类创建起来。好的,那现在呢,我把这部分已经有的代码我先拿过来,这个大家应该能看懂对不对,好,我把这个代码稍微的整理一下。然后这边呢,也给大家整理一下。对。这个pre visit的,它的作用是这个,把这个也记录下来。好,我把这这个类先格式化一下。好,接着咱们就往下写代码了,那么我们来写这个地方首先应该有个构造器。这是没问题的吧,构造器,大家看我怎么写这个构造器啊。
01:02
那就public。Visited ver text,那你怎么构建呢?你首先给我一个N对不对,一个长度,然后呢,Index。也就是说,你得告诉我,你是准备从哪个顶点开始进行处理的,那么我这就写一个this.array。Already,它应该怎么样呢?New,一个int。NS,也就是说这个already already already呢,后面我们这个NS就是顶点的个数。就是我这个already。大小就是你顶点的个数,我这写一下。这点大家注意一下啊,认识传进的1TH,不是HT写错了。TH。
02:00
这个N表示什么呢?诶,表示我们顶点的个数能看懂,Index表示什么呢?OK,这个index表示我们出发顶点。就是我们那个出发顶点,就是哪一个顶点呢?就是我们所说的你你以哪哪个顶点作为出发顶点,比如说我们现在刚才分析的是以G,那但到时这个index就是G对应的下标。哎,就是我们这个出发顶点对应的下标我写在这儿,出发顶点对应到。对应的下标。这个大家能理解哈。比如我举个例子吧,比如g.G这个顶点,那么它下标,它传进来的下标,下标就是几呢?诶就是六。就这么简单,好,接着我们继续写呗。接着我们继续写。这个地方我们要把变量稍微变一下,拿到了,那接着继续往下玩system visited。
03:08
这个是代表它的前驱顶点,那就一样的大小了,也是N。问题吧,紧接着我们继续写这个diss,这个diss在初始化的时候呢,跟前面也也是一样的,对不对,因为你要记录的顶点个数。对,顶点的过程,就是你顶点有多少个,那么第十呢,这个大小跟它保持一致就可以了,比如G点跟其他六个顶点,它到底有多大的距离?好,那现在呢,我们上来过后,大家还记不记得我们这个地势是不是初始化的时候?第十这个数组除了自己这个事情,其他都是65655352,是不是你要处理一下呀,哎,现在呢,我们除初始化初始。
04:02
初始化哪个数组呢?就是DS这个数组。怎么初始化,先把它填,填充为全部都是不可大,就是最大的一个值,Feel怎么写呢?哦,就地史,我们存的就是这一个六。65535。没问题吧,就上来过,就是一个最大值。那么但是有一个例外,就是你自己,你看还记不记得我们上来过后,自己这个是零,因为自己跟自己呢,其实我们认为它的距离是零,但他也不会自己跟自己连对不对,那其他都是6535,自己这个点呢是零,一次把它处理一下,怎么处理也非常简单,就thisd,然后呢,你这下边不就是index吗?我直接给你改成零,也就是说先全部置为65535,然后把自己。这一方四分零代码就写完了,哎,也就是说这样写的啊设置。
05:05
设置出发顶点,出发顶点到哪里呢?呃,出发顶点的。访问距离距离为零就可以了。好,那这块。就差不多了啊,就差不多初始化咱们就写完了,紧接着我们还要写一些辅助的方法,哪些方法呢?这些方法都比较小,但是特别有用,我先写第一个方法,我们先把方法写出来再说他是干什么的,玻璃好的in。Int index,我先说一下这个方法,它是用来做什么的?它的功能是什么?来给同学们描述一下功能,它是干什么呢?判断,注意听这句话判断index。顶点就是index这个下标对应的顶点啊,是否被访问过,访问过后面我们有用。
06:05
访问过后面有用,哎,后边我们遍历的时候非常的有用,那这个反馈就是说,如果访问过,如果访问过。就返回什么呢?返回一个处,OK,否则返回一个false,代码写完了,一句话就搞定了,什么呢?Already。就是在这个数组里面,我去找你这个index,大家还记不记得我们这个already already呢,它是怎么记录的?就是默认为零,如果访问过呢,就会置为一,那这个就简单了,我看它等不等于什么呢?等不等于一,你看如果等于一就代表访问过,那就返回处,如果不等于一,就代表没有访问过,就自动返回一个false,那么就写完了,看懂了啊,下面呢,我们再写一个方法,接着跟着老师思路走,Public void update什么呢?This。
07:06
OK。我说一下这个方法它是干什么的?好吧,走一个,首先呢,有两个变量要传进来,一个是index,一个是N。那这个方法它是干什么的呢?来给各位同学聊聊它的功能,这个方法的作用大家看起来一看就知道大概是要干什么,他是干什么呀?它是更新,更新出发顶点。出发顶点到到节我看看啊,到index这个顶点,到index这个顶点的距离。因为你你到时间到底出发顶点离他有多远是变化的,大家看注意听啊,你原先这个下标你65656535,到了后面他变成二变成三了,是不是你要去根据人家给的这个值把你这个。
08:05
呃,6535重新置为二才是正确的呀,说这里面有一个方法,就是专门来去更新我们这个第十数组的,OK,那更新定时数组呢,你要给我传进来的一个是你要更新哪一个,第二个到底是多大。好,这个也非常的简单,一句话就搞定了,就是diss谁呀,我们的index。Index等于。也就是说,我要记录我的一个顶点G到下标为index一个顶点的距离到底是多少?对,但是什么时候调用会有前提判断,只有在小于你的情况下我才去更新,也就是说假如我在访问点过后,我发现诶到A的。G到A的距离其实是二,所以说我我发现我的二呢小于你6535,我就可以关掉,当然这个二二是因为我现在只有一层,如果你是多层的话,你还得把前区顶点,顶点就是你的顶点,你的顶点到前区节点,以及前驱节点到你这个顶点距离加起来,判断有没有小于前面这个距离,这个说起来有点麻烦啊。
09:16
呃,有点不好理解,大家慢慢跟着写代码,慢慢理解吧。好,紧接着呢,我们还需要一个方法干什么呢?来,同学们看public void update。大家有没有发现我们这个前驱顶点也在变化,因为你在进行广度搜索的时候,前区点是在实时变化的,对不对?所以说我这有个update什么呢?P re,一样的道理,你也把这个前驱节点的pre告诉我,然后索引。给我写清楚。嗯,那么我我把这个方法呢,功能这些也给大家介介绍一下。功能,他要完成这么一件事情,听我说他要完成什么呢?更新顶点,更新顶点的前区。
10:08
哎,前驱。人前区为。为inex的这个节点。呃,决定就说。你你这个前驱节点变化,你要体现出来就这么一个意思,那怎么写呢,非常的简单。哪一个呀,好,Pray等于index。这个大家看懂了吧,就说你你这个就说这下标为P的这个顶点前驱节点变成了这个。啊,全据点更新,顶点顶点全区点点更新,这样说啊更新。顶点更新P。这个顶点的前驱。顶点为index,这个顶点,因为在图里面顶点和节点是一个意思是吧,这个大家看看能不能理解,当然什么时候去调用这个方法,那后面还有一个非常重重要的一个判断,好后面我们还有一个方法来看一下,就是public void get dish。
11:21
Dis,好,我把这帮参数写进去,就是int index,我说明一下这个方法是干什么的啊,其实每个方法前面我们都多多少少已经接触,都已经提到过了,这个方法的功能是返回助听,返回什么呢?返回出发顶点。出发顶点到index这个顶点的距离。因为到时间我要去看哪个最小吗?我得更新呢,所以说这个你要给我提供的方法,我能够拿到一个出发顶点到index顶点的距离,那这个简单return。什么呀?D是是不是?同学们D是谁呀?各位index就完事了。
12:06
那我就循环,诶这地方应该会返回一个int才对。代码就写完啊,这个index就是你要想得到的这个顶点,就是这个顶点距离我们出发顶点的,嗯嗯,这这个index就是你你想得到哪个定点距离我们出发顶点。到距离,你把这个inex传进来就可以了。好,同学们,那到此为止,到此为止,我们这个VZT的最核心的方法就写完了,那现在呢,其实我们就可以尝试着来编写一下,哪个呢?各位同学,现在我们可以尝试着编写一下第十,呃,就是我们这叫狄杰斯特拉这个算法了,来玩一玩呗。哦,可能还有一部分代码没有写完啊,但是现在已经可以尝试着写了,这里面还有一个重要方法没有写,就是这个方法。
13:00
继续选择并返回新的顶点,还没有写,但是我们先把第一步这块给他走一下再去写。嗯,下一个的怎么去选,选取下一个新的访问顶点,再像这样做一遍的过程,这还差一个方法,待会我再写好吧,因为大家现在需要看一个效果,不然的话听懵了,我来写这个狄杰斯特纳算法第一节。迪杰斯特拉迪啊,这个。第一。狄杰。算了,从这拷贝吧,因为的杰斯特纳这个这个名词呢,它并不是一个常用的。算法。实现。OK,算法实现,那么我们怎么写呢?来,同学们跟上我的思路,Public void。我就简写DS节。你给我写个index。这个index代表什么意思呢?来,我给他写说一下,这个dex代表你的出发顶点对应的下标。
14:07
注意听啊,表示表示出发顶点对应的下标能理解吗?好,那这个index拿到以后,下面我们首先要六出这个VZT的ver ver的一个实例大小是多少,是不是就是你的顶点的个数索引,就是你传接索引。好,这就得到一个这个玩意儿了。好的,当我这简写VI好吧,微微也行,就叫微微吧,叫VV比较好记。为例,那么当我们把这个做完了以后。我们先来验一下,就是当我们六六完了以后,我们看看它是不是得到了。这么这个VI里面的三速度是不是变成这个样子了好不好,我们先来玩一把,先下个断点。
15:01
来测一下呗。因为你有时候不去测试很难,很难看到这个效果,大家也没失去一个调试的机会了。测试一把狄杰斯特拉。第一节斯特拉算法。我现在先测一下啊GRGRa.DJ是他,我们就写六。来,各位同学,我把断点先下到这个位置,我们来跑一下。如果没有什么问题的话呢,我们第一个那个图应该能够拿到。来,各位朋友。现在呢?我们追到我们的这个算法里面去进去了。好,同学们可以看到微微。现在这里面呢,都是空的,你看。是不是现在这里面都是空的,还没有,还没有进行这个初始化,好各位同学,现在呢,我往让它向下走一步。好的,各位同学再来看。我们再来看啊,同学们看此时此刻,我们看一下这边的情况是什么样子的。
16:05
我们重点看哪一个呢。我们重点看VI里面的这几个数组。诶,VR这个数组现在我们看在这有没有。搜一搜,哎,果然有V有微微了,微微我们看奥。Already是不是全零了?因为你现在还没去走那个动作吗。所以现在是权力第四呢,你看。这个是不是65536553565350好,前驱节点目前应该是全零正确,好现在呢,我们接着往下写代码,还有一个重要的方法。
我来说两句