00:00
各位,我们继续来讲解下一个图的广度优先便利的这么一个算法。那首先呢,我们来看一下何为广度、优先、便利,先把它的基本事项给各位同学做一个介绍。图的广度优先搜索呢,也叫broad search,一般简写为BFS。OK,那么它类似一个分层搜索的过程。呃,待会呢,我们在举例的时候,大家可以感受到这一点,它是一个类似于一个分层搜索的过程,广度优先,便利需要使用一个队列,它这个队列的作用是这样子的,就是当我们去遍历,比如说遍利abcd的时候,我先把这个A便离过后把B放进去,把B放进去过后再把如果访问到C,再把C放问过去,好,那么如果在这个过程中有一个临界点访问不到,我就从这个队列里面先把B提出来,然后让这个B以这个B为起点,再去便利,看看能不能把C后面的节点遍利到,诶,它是这样子的,所以对联它是很有用的。
01:12
那么他用这个队列。呃,需要用一个队列以保持保存或者要保持都可以啊,保持访问过的节点的顺序,以便按照这个顺序来访问这个节点的临界节点。对,那这个过程大家可能对这个话还是不太理解,对不对,我们来看一下它的一个便利算法的大致的一个步骤。那么它首先访问初始节点V,并标记为把这个V这个节点标记已访问,第二点把这个V加入到队列,当队列为飞空的时候呢,继续执行,否则算法结束。注意,这个所谓的算法结束指的是对这个V这个节点算法结束。那如果说呃,如果说这个V后面还有别的节点呢,整个这个过程还是要有一个for循环来套用的。
02:04
好,我们我们现在说的是对这一个节点啊,对这一个节点而言的一个算法结束。呃,那么呃,第四一步出队列取得头节点UU,它代表头节点,那么查找这个节点U的第一个零节点W。若节点U的临界节点W不存在,则转到三继续执行,否则就执行下面三个步骤,哪三个步骤呢?如果这个W没有被访问,那么标记访问并。访,并输出这个访问,呃,然后再把这个W入队列,W入队列的作用就是代表这个队列已经被访问,而且它保持一个被访问的顺序,也说这个W的访问的顺序也被记录到队列里面了,然后查找节点U的GW临界点后的下一个临界点W,然后转到下一步,嗯,其实这个整个这个算法他已经说的非常清楚了。
03:03
但是我相信啊,如果说你是第一次学习,广度优先,便利你,你也很难理解他在说什么。或者说。这个步骤到底是在说什么,也很难理解对吧?那没有关系,我下面呢再举一个实际例子,大家来体验一下,它是这样子的。我给大家描述一下这个关系,假如我们这个广度优先是从A开始的,那你可以想象好像这有个A,就当前呢,有一个索引指向我们这个A了,他先访问自己,所以说A就出,A就访问到了,看到没有。他把A访问到过后呢,他看A的下一个临界点B是否能访问AB是能访问到的,于是把B也输出来,注意听。把B数出来,然后再以A,注意看啊,这个地方就是深广度和深度不一样了,如果是深,深度优先,它是以这个B这个节点开始去找。开始去从这个B的第一个临界节点一个个找,看看哪一个能够返回到C是吧。
04:05
哎,知道我在说什么吗?就如如果现在我们假定是光是刚才讲的深度优先。他会怎么做,他会以B这个节点为一个新的节点为或者叫新的一个起始点,然后以B这个节点呢,按按照它这个顺序一个一个的看,他先看B的,B的第一个临界点为A,但是这个A呢,已经访问过了,所以说他他会不访问,然后再看这个BB跟自己,他肯定要跳过去啊,因为零嘛,零它就相当于说呃跳过,然后呢,这个时候他找到C了。也就是说如果是深度便利的话呢,其实这样它也它会访问到C,但是是从B这个节点过去的,明白吧。啊,这点大家要清晰的知道啊,我撤回去,那么如果是广度优先呢,它是怎么样呢?注意听广度优先它是让这个A访问到B以后呢,他再去以A这个节点,以A这个节点为起点去找它的W,就是现在这个B节点的后极节点,其实就是C,他发现C呢也访问到,于是他就访问到这个C了,也就是说他是在这一层。
05:14
在这这个A以A节点这个这个节点去找B节点的后继节点C,我能不能访问到,当然他这个时候访问到了,因为它不到下一层来访问到,紧接着他还以A这个节点。为前去以前面这个节点去找他现在的这个后机节点的W,呃,这个C有没有。有没有可能访问到D,这个时候很遗憾,他发现找不到。所以这个时候找不到怎么办呢?大家还记不记得这个B已经入队列了?这个B已经在队列里面了,而且它是队列里面第一个,因为A访问过后呢,其实第一个以前被弹出去了。这个时候他就从这个队列里面把这个B取出来,然后再去B找,B找也是一样的,他先先找B的第一个A,诶发现A这个点已经被访问过了,就跳过,然后在这个零肯定它就不访问了,零我们代表。
06:10
代表不不能访问对不对,然后他这个是叫C,哎,C是不是也也已经被访问过了,因为他还是要标记这个节点是否被访问,诶这个时候他发现诶非常幸运,他发现D能够访问到,看到没有,所以说这个地方他又把这个D打出来了。有这个顺序,你发现还是一样的,但是呢,这个时候这个D可不是从C过去的,而是从B过去的啊不,这个这个时候的D啊,这个时候的D是从这个C,呃,是从B这个地方返回到这个B的,明白这意思吧。啊,是这样子的。那你如果那你如果是这个深度变的话,情况就不一样了,对吧?诶。至少这个过程不一样吗?至少这个过程不一样,OK,那这个时候呢,他紧接着再以这个B啊,再以这个B继续去看它下面这个E能不能访问呢,发现也能访问,OK,这个时候呢,又访问到了。
07:06
好,这个时候,当整个这个节点。便利结束过后,他还是要进行一个递归的,诶也就说也也就是说他怎么知道怎么什么时候退出呢?因为你刚才是以A进去的,又是B进去的,然后再去再找这个CD,再走一圈,发现都访问过了,就退出,整个这个广度优先便利了,所以说你会看到这个过程最大的区别是它先分成,就说我先把这个A能访问的全部访问到。全部走完,然后AAA实在是访问不到的呢,就从这个B里边。再去找,而原先深度不是这样的深度,如果找不到,它是以找以上以这一层去找的是不是,诶这点大家要注意一下啊,同学们要注意一下就可以了,好的,嗯,整个一个。简单的思想我们就聊到这儿,那关键还是我们代码来实现。
08:05
关键代码来实现对不对?好,思想讲到这,我们用代码准备给他走一下。
我来说两句