00:00
各位同学,我们用代码给大家把深度优先给实现一把。好,首先我们刚才讲过,就是在整个过程中呢,我们有一个标记对不对,有一个标记什么什么为已访问的这么一个。这么一个要求,那这个时候我们可以先定义一个数组。哎,对应一个数组,我们叫不这样一个数组。干什么呢?记录,记录某个某个顶点或者节点是否被访问过。是是否被访问过,这个是可以共享的,呃,那么这个,嗯,这个。布尔数组呢,我们可以先把它创建起来,比如说取个is visited,就是是否被访问加个数组。呃,类型呢,咱们就叫玻璃类型。Body。OK。这么一个数组。
01:01
好的,那大小为多大比较合理呢?各位同学,那么我们我们知道我们的节点,我们这个顶点的个数其实最多,呃,最多的也就是根据我们这边传进来这个N,其实我们知道最大是多大对不对,我们是知道有多大的,我先我这先写一个好吧。不对。第一个不领,那么大小呢,我们目前是五个,其实这地方是可以传进来的,因为我现在有五个顶点,那我至少得五个对吧,所以说这地方先写个五,实际上这个地方呢,我们可以把这句话放到我们的构造器里边去更合理,是不是这样子的?同学们好,我把这句话放到这来。哪里呢?这边先不去管它,先定一个这句话放过来,放哪,放到我们的构造器。是这样子吧,同学们好过到气放到这个位置,那么这个地方我们就不写了,诶这样子就比较合理。
02:00
这个是记录某个节点是否被访问,好,这个写完了,紧接着我们继续往下看。继续往下看。嗯,因为在整个这个深度便利的过程中呢,我们是不是有几个动作是要得到他的第一个临界节点。就是得到他第一个临接节点的下标,这个W代表它的一个下标。啊,这个零点下边如果说我返回一个负一,代表没有,如果返回的是非负一,那是这个临界节点下边是多少就是多少,好,我先把这个方法写出来,注意听啊,我们先写一个方法得到。得到什么呢?第一个临街。临街街临街这个写错了,临街。节点的什么呀,下标就下标呢,就是后面我们要用到的这个W,那就开始写public in guide first,大家看这个方法能不能看懂啊,First。
03:05
什么呢?诶,这个应该叫做名字临界啊勒。Labor。后。是这样写吧,那这个单词应该这样写比较合理,对吧,邻居嘛,然后呢,这边你你要把什么呢?把你这个节点的下标给我,我才能返回你的下一个是不是把这个索引给我,那我肯定要变利一把了,那变利的时候呢,我先用个节等于零,节小于多少呢?肯定要进行一个遍,例Y。Vertex sides。好,咱们结加加结加加做一个判断,如果说我们的这个边。就是我们这个矩阵吧。这个AA意思它的什么呢?OK index。Index解,大于零说明什么?
04:01
是不是说明它的下一个临界点是存在的,所以说我就直接返回一个勾,否则整个for循环结束过后,我发现没有返回,我就返回一个负一就完事了。OK,那我这做一个注释。做一个猪是什么呢?就是。就是返回是如果存在,如果存在A,如果存在。存在就返回对应的下标,否则返回一个什么呢,负一。是不是很简单啊?那么就行了,那下一个呢,我们还有一个方法。什么呢?要这个方法大家注意啊,根据前一个前一个临街。临街。节点。的下标就是前一个连接节点的下标来获取。来获取什么呢?来获取来获取下。
05:04
一个节。呃,该怎么想啊,下一个临界节点,对下一个临街。临界节点大家看理不理解,我要根据前一个临界节点的下标。前一个临界点,下面来获取下一个临界节点,这一句话呢,我们先把它写出来,大家看,OK public。好,Int。In,什么呢?我嗯,取个名字叫做get net,因为下一个了。好,Ho。HBO2HBO好,你给我传一个什么呢?传两个值进来,一个是V1,一个是V2。好的。那么我拿到V1和V2过后,我怎么办呢?我仍然进行一个for循环。我仍然进行一个负循环,那就是解,如果等于V2。
06:03
加一,我要加一个一啊,然后呢,解,如果小于还是这个范围呢,仍然是在我们这个。这个集合里边结加加一个条件来了。因为下一个嘛,肯定是夹一下,然后呢,如果还是一个条件,如果我们这个。A,什么呀,它的V1走。解,如果大于零,那么说明什么呢?说明存在,我就返回。这个对应的下标,如果整个for循环结束以后没有,我就返回复议。再看一下啊,这个是根据前一个临界节点的下标来获取下一个临界节点,因为我得知道我的下下一个临界节点是什么。对不对,我得。知道下一个临界节点是什么,说这个人必须得有,好,当我有这两个方法过后呢,这个代码就可以写了,现在我们可以写这个深度。
07:08
深度优先这一个便利算法。那现在呢,我们就来开始写这种方法,这个方法呢。我们开始写啊呃。这个怎么写呢?我们写个诗,写个这样的方法,Public。Void。我们就叫,呃,叫DFS吧,简写DFS。好,这个时候。这个时候大家想,大家有没有,有没有注意,就是在整个我们在整个递归的过程中,我们始终会有一个动作,什么动作呢?就是判断有没有被访问。是不是就在整个这个过程,我们始终要判断这个节,这个节点是不是被访问,有没有被访问,因此呢,我这边是需要把这一个数组拿到的,你不给我这个数组,我没有办法去判断。所以说is visit这个。
08:03
这个数字我是要的,并且把这个下边给我。对,也就是说你现在,你现在是要去访问,你现在去要去访问这个节点。你要去访问这个节点那?那也就是说到这一步,到这一步其实已经相当于进入到了第一步,明白我的意思吧,你可以理解。我们现在是在访问第一步,你可以简单理解成这个I呢,就是第一次进来就是零。明白吗?就你可以理解这个I第一次。第一第一次啊,我们说是第一次就是零。那如果是零的话呢,就比较好理解这个东西了,那首先首先我们访问该节点,什么叫访问该节点就是输出嘛,说白了就是访问就是输出,那就输出这个节点了,没问题吧。怎么输出,是不是get?
09:02
我们这是不是已经有写了一个get value by?Index把爱放进去,为了好看呢,这个地方我们可以写个加。OK,好,可以写个箭头,就代表这个访问了,下一个是谁,这个意思这个意思好,那你一旦访问了,你下一步是不是应该把这个访问过的这个节点置为已访问。是不是这样的道理啊,将。将该将这个节点,将这个节点设置为,设置为已经访问过,能理解吗?那你怎么把它设置为已经访问呢?那就1VISITED下标为I的这个玩意儿设置成。处。就已经访问了,好同学们。那么刚才我们讲过,你访问完这个节点以后,就要以这个I这个节点为当前节点进行深度便利,是不是已经到了这一步了?
10:02
标记是不是到了第二步,查找这个节点V的第一个临界节点W有可能有,有可能没有,是不是这个方法刚才已经写过了呀,诶,我们就用这个方法了,来吧,W等于什么玩意儿呢?Get。First。Neighborhood。那这个时候下标显示I,注意听这句话是干什么?干什么好这句话,这句话其实就是老师在这写的这么一句话理解。能理解这意思吗?查找V节点V,当然这个节点应该不叫V了,叫I吧,好吧,叫节点I的第一个零基节点W,那刚才我们讲过,嗯,如果它返回一个负一,代表没有,如果返回不是负一,那就是有,那是不是这样子的,我们这是不是有有这个逻辑?如果存在我们怎么办?如果不存在怎么怎么办?好,我们先说存在的问题好不好,那存在的话呢,是不是我们有个外循环,为什么是外循环呢?因为它只要存在,它就去判断是否访问,呃,有没有访问。
11:09
然后就这在这不停的递归了,看到没有说这个地方一定是个Y循环,所以我们就应该这样写的Y,如果这个W锥T不等于负一,说明什么找到了。是不是说明有啊,说明有。说明有临界节点,说明有吗?那如果有的话,诶,你是不是还得判断他有没有被访问过,因为它有了,它有它有可能是因为回溯回来的,那你已经访问,你不能再访问了吗?所以说你要判断有没有访问过,那就写意什么样,诶假如你没有访问过is visited的,所以呢,下边根是几,是不是W啊。是不是W,因为你现在W就是它对应的这个下标嘛,好,如果这个玩意没有被访问过,好,那你就可以访问了,那也就说没有访问就进入到我们的对W进行进行访问,然后就递归好,访问的时候就做这样一个动作就行了,什么deep。
12:06
D啊DDFS啊DF,把这个EV体的传进去,这个I是多少同学们?是不是就是对这个W进行访问了,那你又递递归进去,他又把这个节点打出来了吗。是不是这个道理好,但是有一种可能性,同学们。同学们有这种可能性,就是这个W是是存在的。但是呢,他已然被访问过了。是不是就说如果朱婷,如果这个W这个这个节点。节点。已经被访问过怎么办?如果他已经被访问过,按照我们刚才这个逻辑,它是如果他已经被访问过,我们就应该去查找临界点的下一个临界点,就是临接临临接节点的下一个临界点。那应该怎么做呢?刚才那个方法不是已经讲过了吗?就一句话的事儿,就应该W。
13:03
等于get。Next。Neighborhood。好,这个地方应该是I和W。是不是这样一个这样一个关系啊,就是你这个I是你。这个正在被访问的节点,而W是你,什么呀,是你?找到的下一个,但是呢,他已经被访问过的这个这个节点的位置,就找到下一个,能理解我的意思吧,找下一个,好,这个while循环结束以后。这个while呢,就在不停的做,不停的做,不停的做,但是大家有没有发现我这还少了一个动作,哪句话呢?诶,他有一种可能性是W不存在,它如果说W它不存在,是不是等于负一,等于负一是不是它会退出这个DDS。你现在其实只是从零开始走的,你还没有考虑零的下一个点,一二这些是不是没考虑过呀,好同学们,所以说我们这个DFS呢,还有一个动作要把它套起来。
14:04
要实现我们刚才这个动作就是回到第一步,然后从V的下一个节点继续,那这个应该怎么体现呢?好的同学们,我们这里面还有一个方法是对什么呢对。对这个DFS进行一个重载,这注意听啊,因为你这样进去只从一这个节点走的,你第一个节点走完了过后,他如果没有访问,没有访问是不是你还是走。这个第二个节点也也就这么来一把呀。是不是也得这么来一把?因此你要对它进行一个重载干什么呢?便利我们所有的节点并进行。这个DFS。是这样子的吧,你不能说走完一个节点,这个A走走完了过后他不行,你就完事了。就好像你这样走的,怎么走?哦,A走了,ABC走到ad走不下去,我不,我不玩了。
15:00
那A走不下去,他有可能是他的第二个这个B这个节点,它能够跟这个跟这个地关联吗?你不能说你不走了呀,是这样的道理吧。好,所以说我们这边还要这样走一把,应该怎么写呢,我就不改变名称了啊,叫public。我们。还是一个贸易的注意听,那这边我们仍然写DFS,没问题吧,同学们。这面不传参数,这面就是什么呢,便利所有。的节点。进行DFS,其实这个就是有点回溯的感觉啊,有点回溯的感觉。好,那这个代码就非常简单了,For循环各位朋友,For循环I ti。等于什么呢?0I小于什么玩意儿呢?Get我们所有的这个节点数量,我们一共有多少个节点呢?是不用这个来接,其实我们就五个,那么I加加。哎,佳佳,你第一次上的是什么什么东西啊,我们加一个条件,如果is visited你还没有被访问过,因为这样可以提高我们效率,I如果他没有被访问过,好,我们就是便利的时候,我们再加一个条件。
16:13
因为在回溯的过程中,有可能某个节点已经被已经被这个访问过了,所以说我加一个条件,其实什么呢?好,咱们这个地方就应该deep应该这样写的吧。D。这稍微有点DFS。DF,谁呢?就是刚才我们写的那个is visited传进去。Is。Visited,然后呢,是谁就是一个I就完事了。也就是说我们到时间调的只是这个DDFS就可以了。是不是有点绕啊,其实也不是很绕,其实说白了就是老师把刚才这个12345的这个语言用文字的,用这个代码形式给大家做了一个翻译嘛。做一个翻译虽然有点有点麻烦,但是也不算太难,对不对?如果还有问题,待会我们可以用这个debug来走一圈就完事了。好,同学们,代码写完我们来测一把。
17:06
我们来测一把,来,各位同学,现在呢,我们测试一把。诶,测试一把我们的深度,我叫DFS电力是否OK?便利是否OK,那走一个就行了,来走一个。好,这边我说句话叫做。深度便利深度便利。OK,那很简单,我们graph。点我们的DFS就搞定了。对吧,D就搞定了,那这个时候其实我们可以把这个方法呢,做成一个私有的,对吧,因为你不让他直接调。代码就写完了,来各位朋友运行一下,如果没有出什么问题,他应该是A。B,跟我们刚才分析一样,Abcd。应应该是这样一个流程。OK运行。好,我们运行过后,我们发现这个结果呢,OK ABC de正确,Abcde为什么没有达到一行呢?诶我们看一下啊,没有打到一行是因为哦,我这个地方呢,来一个换行,怎么这样子会好看一点,对不对,放到一行呗。
18:18
大家看一下这个顺序,A访问,访问bc de OK,这个顺序就是我们所所谓的深度便利的一个流程,大家看能不能理解。啊,能不理解,那这样子,如果说同学们没有理解的同学呢,可以适当的我们来调试一把。来吧,我们调一调啊,调试一把,大家再加深一个认识就可以了,来,我。不走完啊,我调到几步就调到几步就行了,来运行一下,运行一把来debug s一下。各位朋友,跟上我的思路。看看跟我们刚才分析的是否一样啊,来捋一捋思路,先追现在A打出来了吗?没有打出来,没有打出来,进去追进去,OK,大家看,首先这个哥们他先去看你第一个A这个节点,因为你是从A节点开始进行深度便利的嘛,那第一个肯定不,他肯定是没有访问过,所以说他会进到这个里面来。
19:16
进来了吧,进到这里面来看,这个I呢,现在是等于零的,是不是我们就追进去,各位朋友追进去了,追进去过后是不是这个时候先把A就打出来了,说诶哥们A已经访问过了。那么A访问过了过后,各位朋友,我们看是不是他去找A的下一个就是一节点I的第一个临接节点W。那应该是得到哪一个了呢?如果这个没有错的话,他应该得到了我们B,是不是这个道理,同学们往下走得到了吗?显然得到了是一,一就是我们的B吗?那现在这个时候呢?接着往下走,现在W呢,它是不等于不等于负一的,于是进到这里面来,那么B这个节点有没有被。
20:01
B这个节点有没有被访问呢?显然B还没有被访问过是吧,只有第一个节点被访问了吗?那现在又进入到这里面去了,肯定要进入进去,进入到这里面,他又开始我们这个所谓的。深度变离,那这个时候呢,要往里面追啊,要往里面追,你进去了,往里面追啪走进去,哎,这个时候你会发现呢,这个I已经等于一了,因为他在访问A的第一个临接节点,那这个时候往下一走,啪,A又把B。弄出来了,并且把这个B呢又标志为处啊,就说B这个节点对应的下标标志为一个处,也就代表我们第第二个节点已经被访问。
我来说两句