00:00
各位,我们来看图的遍历。首先呢,我们先来给大家讲解一下图的深度优先便利这个算法。别这路啊,首先我们先看一下何为图的便利,所谓图的便利呢,即是对节点的访问,就是我们把图这些顶点或者节点进行一个访问,那么大家想,一个图有那么多的节点,如何便利这些节点呢?肯定需要特定的一个策略,目前来说呢,主要有两种访问策略,第一种我们称之为深度优先。第二种,我们称之为广度优先。那么我们先给大家讲的是深度优先这个它的一种基本思想,来同学们我们聊一聊,我们聊聊这个话题。那么何为图的深度优先?首先看图的深度优先,它的对应的英文的名称叫deep first search,简简写的话就是DFS,也就是说你们以后看到别人写的DFS呢,就代表是深度优先这种搜索算法。
01:08
那么它的这一个基本思想是什么样子的呢?来聊两句,我这里总结了三句话,深度优先便利,它是从初始访问点,初始访问节点出发,就是从你定的第一个,你定的那一个初始访问点,初始访问点节点可能有很多临界节点,对吧?它可能有很多,那么深度优先便利的策略是首先访问。首先访问第一个临界点,就是说假设你定的是V。把这个V访问过后呢,再紧接着访问V的第一个临界点。你,你的节点不是有顺序吗?就看它的下一个临界点是什么,OK,然后再以这个被访问的临界点作为初始节点。访问它的第一个临界点,就说比如说我把这个V1访问到V1 V1的下一个顶点。
02:05
它的第一个临界点是V2。他把这个V2访问了,再以这个VR大家看这里啊,再以这个被访问的就是V2被访问的意念作为初始节点,再访问V2的。第一个临界点,假设V2呢是下一个临界点是V3,好,那就是从这个V2这个地方开始去访问V3。好,这个地方大家理不理解,那有些同学说,老师假设V1和V3也有一个连接怎么办呢?注意,如果是V1和V3也有连接点,那么它其实也是从这个顶点,就是你刚刚访问的这个V2,这个顶点去向这个V2V3进行访问的,并不是回到V一再去访问。哦,这个深度优先是这条线。大家再看一遍啊,再看一遍深度优先,我把这个换条换换换一根线啊,换个颜色B换成蓝色,诶换成蓝色的。
03:00
换成这个蓝色的好,这样就可以了,深度优先是指的先把V1访问V1访问完V1 V1的第一个临界点是V2,再以V2V。为初始顶点,再去访问它V2的下一个顶点。它也是是从V2去访问V3的,而不是从V1去访V3的,如果是V1访问V3,这就成了广度优先的,好,这点大家知道就可以啊,待会儿我们还会深入的再说广度优先也就大家明白这个道理。可以这样理解,深度优先算法,每次都在访问当前节点后,注意听,每次都在访问当前节点后,首先访问当前节点的第一个临界点。哎,就是刚才你不是你把V2访问了过后呢,A再以V2为起始点,再去访问它的临界点,明白好,我们可以看到这样的访问策略呢,它是优先向纵向挖掘深入,它是一直往下走。
04:00
啊不,纵一一直优先是向纵向挖掘,而不是对一个节点的所有临界点节点进行横向编离,就是呃不是说呃,我把V1我V1和V20连的,我我先从V1出发把V2访问了,再从V1出发把V3访问了,不是这样子的。OK。从这里我们可以看出来,深度优先搜索显然是一个递归的过程。是吧,是个地位的构成,OK,那么这个呢,只是它的一个基本思想,那么我们再来看它的一个具体的算法的一个步骤,注意听讲,那么具体来讲应该怎么去理解呢?啊,注意看,我这里总结了五句五句话,待会呢,还有一个具体案例分析,大家就彻底的明白了,何为深度优先,因为现在有很多这个书上在讲,很多同学也没有听明白,所以说我这讲细一点。深度优先是指。访问初始节点被并标记这个节点已访问,那你要把它标记已访问,肯定你你得有个变量对吧,你得有个变量的记录,这个节点被访问过了,那一般呢会用一个数组,比如说我们用一个玻璃数组来表示哪一个节点被访问了。
05:12
那么查找这个V的第一个临界,临界点W,假设V下面的临界点是W,我们找到了。好找到了,如果这个W存在,因为因为它有可能没有嘛,对吧?啊,有可能没找到,呃,找查找节点第一个临界点V好找到存在,则继续执行第四步,如果这个W是存在的啊。W存在的。就往第四步走,如果这个W没有访问过。呃,没有访问过,因为这个W有可能被访问过,对吧,所以说他如果没有被访问呢,对W。这个进行深度优先便利,即对看这话把W当做另外一个V,然后再进行这个123的操作。实际上就相当于说,诶把它找到往下走,比如说我们又找到一个新的节点VW,再找到V2,上面又有一直往下纵向走,就是以这个点节点在出发开始往下走。
06:13
好。那那大家看。查找这个这个不停的做123就不停的这样做,那么有一种可能性,注意听这句话啊。如果这个。这样的一个情况。在市。如果说我们查找这个临界节点,V的V的这个W临界点的下一个节点。就是什么意思呢。就是说如果我们这个W他被访问过了,他是第五步指的是这个意思,就是说VW是存在的。他首先是存在的,呃,但是这个W它已经被访问了。大家明白什么意思吗?啊,如果这个W已经被访问了,那么查找节点VV的W临界点,下一个节点就是再向这个W下个节点再去找。
07:06
然后又回到123。哎,是这个意思,那么第三第三条路呢,还有一种可能性,就是你这个W不存在。是有有种可能性的吧。就你下个临界点W不存在,不存在呢,我们就回到第一步,然后从V的下一个节点继续继续执行。啊,可能有些同学已经听蒙圈了,都不知道老师在说什么,对不对,没关系啊,现在如果这12345还不明白,我们待会又走代码,再来看一个具体的案例,可能大家就相对清晰一点,来吧,我们再走一个案例,我说了这个呢,稍微有一点点麻烦啊,虽然不是很难,但是有点麻烦,我们针对这个12345,这个呢,我们给大家举一个具体的案例分析,大家看是不是能明白,比如说我们就以刚才我们建的这个图进行一个深度优先遍例,它会怎么走呢?来,一步步走。
08:01
嗯,先访问初始节点V,假设我们定的是从A开始走。因为A是我们的第一个顶点嘛,我们建这个图的时候,是不是先把A加进去,再加B再加C,再加C,再加B再加E的,好我们从A开始走,那如果是从A开始走的话呢,上来看,先把这个A标记为一访问,所以说你可以认为我们已经把这个A输出了。理解。好,而且已经把这个AA标记成已访问了啊,查找这个节点V的第一个零节点,好,我们知道我们在这个链表里面,我们这个节点存放的这个顺序,大家还记不记得是不是A。B。C。De,啊,你A的下一个临界,临界点是不是?倒闭了呀。是不是到B,那么我们大家B存在吗?显然是存在的啊,你下一个临界点B吗?B存在,B存在则继续执行式。
09:07
那么继续执行是。W,呃,WW是存在的,存在则继续进行这事,然后他就看你这个W有有没有被访问过,显然你这个B还没有被访问过吗?没有被访问过呢,他就去访问,访问的话就把这个B。输出了,哎,也就是说A访问了过后就访问这个B了。呃,访问完了过后呢。他把这个访问进行这个深度优先,其实就回到了,就是说又访问这个BB吧,好又以这个B为节点,访问B的下一个临界点,大家看你你B的下一个临界点是什么呀。B的下面节点是不是C啊。B的下一个临界点你看吗?从这可以看B的下一个临界点,因为它是这从这开始找了。找这个C,他找到了,这个是它的下一个临界点,因为你这个现在已经访问到下边为二了嘛,所以它访问到三返问这个他发现这也是这也是对的,好,这个时候他又把C说出来了。
10:10
好,C又输出来了,C又输出来以后,大家看这个地方,他把C输出来过后呢,他继续以C。呃,我就不说那么多了啊,以C为这个出发点,又去找C的下一个顶点,好,同学们看C。哎,来看C的下一个顶点应该找哪去找了呢?C就应该相当于说我们已经到到这来找了啊,在矩阵里面的来看,就是叫叫做C这个点,它去找下一个点是D。是不是D,但是大家看到C和C和这个D里面呢,它并不是连通的。它并不是连通的,就好像我们认为这个W,它的下一个临接点实际上是没有找到的,因为这个里临接代代表C和D是否连接,他发现没有找到。
11:02
好,没有找到的话,这个D就不能马上输出,那怎么办呢?好,相当于就到这来了。就相当于说你这个地方W不存在,它又回到了。这一步。明白,他又回到了这一步,回到这一步呢,他把这个。这个第二步就是你上一步的这个,这个你你原先最先进来,是不是从A进来的呀。是不是回到V的下一个节点,我问大家V的下一个节点是什么呀?是不是B呀?因为你刚才是一直从A进来的嘛,现在回到下一个节点,那就B好,它相当于又从B开始来看B有没有跟D关联呢?诶大家看B和D它是关联的。或者直连的,于是乎,他就把这个D数出来了。OK。OK。好把这个地说出来以后呢,他。
12:00
又去查找B的下一个临界点顶点啊,你看啊,找到一个B的下一个临界顶点是什么呢?是E。是一,而且它确实联通的。于是他在这个地方呢,又把这个E给输出来了。好,溢输出来,艺输出来过后,后面再去找,其实这个整个就已经变定完了,到它外面有一个负循环,他发现呢,Abcd已经便利完毕了,因为他去要去判断我的整个整个这个走的过程中,是否这这些节点是否是不是全部都已经便离过了,也就是实际上他把这个E输出来过后呢,他发现E没有这个点点,他还会从,他还会从这个B的下面再去走一下,这个CC去走的过程中呢,他在进行这个深度优先的时候,他发现所有的节点都已经被电离过了,所以就退出,他还从D还要走一边。但是呢,发现他在走D的时候,他发现所有的节点也已经走过了,也会退出,明白吧,其实他还是有个回溯的过程。
13:02
啊,有个回溯的过程,好了,我我这样讲,大家看看大致明白不。啊,是不是有点还是有点不明白对吧?啊,这这有点不明白,也也也也是正常的好吧,那整个这个结果呢,我们可以看出来是A。B。C。De就完事了。好,这是老师一个分析过程,那么嗯,这个地方你不管怎么讲哈,就不走代码肯定是很难理解的,但是大家大体知道,首先你大体要知道深度优先便利的一个基本思想,这点一定要分析出来,就是说它是以你比如说我访问AA访问了过后,访问能我看看下我我下一个临界点点是B,我有没有跟他连通。OK,如果联通,我就把这个B返问到,然后再以刚刚返问过这个节点又为出发点,看看下一个临界点,因为你B的下一个临界点B已经访问过了,下一个就应该是C,看看B和C是否是联通的,如果是连通,我就继续说,然后呢,这个这个再以这个点为出发点,看看下一个临界点,下一个临界点啊,已已经变成D了嘛,就看DC和D是不连通,如果连通继续输出,如果在这个过程中发现不连通,那么它就会回到这个。
14:13
回到这个这个地方啊,回到什么呢,回到。回到就是你刚才这个A走的这个位置,继续往下重新来一圈啊,当时他他是从下一个位置,刚才我讲的那个不是我们走到C是走不下去了吗?走不下去了过后呢,他又回到这个D。因为你刚才走的是A嘛,那就从B开始去看B这个节点能不能跟这个D连接啊,它是其实那个跟跟D输出的时候是这个B跟它连接,从B这个节点找到这个D的明白吧。哦,我不知道我有没有讲清楚,好了这样子,嗯,大体知道了,过后呢,我们有个整体印象过后,下面我们走代码,代码一走,其实大部分同学也也都能够明白,因为代码说的更加的精准,好的同学们,那关于我们这个深度优先便利的一个算法分析图解,我们就先聊到这儿,好吧,就先聊到这儿。
我来说两句