图的深度优先搜索

Published on 2016 - 06 - 20

DFS算法思想

深度优先搜索(DFS)是一个递归过程,有回退过程。DFS算法的思想是:对一个无向连通图,在访问图中某一起始顶点v后,由v出发,访问它的某一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问;……;如此进行下去,直至到达所有邻接顶点都被访问过的顶点u为止;接着,回退一步,回退到前一次刚访问过的顶点,看是否还有其他没有被访问过的邻接顶点,如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再回退一步进行类似的访问。重复上述过程,直到该连通图中所有顶点都被访问过为止。

接下来以图1(a)所示的无向连通图为例解释DFS搜索过程。假设在多个未访问过的邻接顶点中进行选择时,按顶点序号从小到大的顺序进行选择,比如顶点A有3个邻接顶点,即B、D和E,首先选择顶点B进行深度优先搜索。

对图1(a)所示的无向连通图,采用DFS思想搜索的过程如下。

  1. 从顶点A出发,访问顶点序号最小的邻接顶点,即顶点B。
  2. 然后访问顶点B的未访问过的、顶点序号最小的邻接顶点,即顶点C。
  3. 接着访问顶点C的未访问过的、顶点序号最小的邻接顶点,即顶点G。
  4. 此时顶点G已经没有未访问过的邻接顶点了,所以回退到顶点C。
  5. 回退到顶点C后,顶点C也没有未访问过的邻接顶点了,所以继续回退到顶点B。
  6. 顶点B还有一个未访问过的邻接顶点,即顶点E,所以访问顶点E。
  7. 然后访问顶点E的未访问过的、顶点序号最小的邻接顶点,即顶点F。
  8. 顶点F有两个未访问过的邻接顶点,选择顶点序号最小的,即顶点D,所以访问D。
  9. 此时顶点D已经没有未访问过的邻接顶点了,所以回退到顶点F。
  10. 顶点F还有一个未访问过的邻接顶点,即顶点H,所以访问顶点H。
  11. 然后访问顶点H的未访问过的、顶点序号最小的邻接顶点,即顶点I。
  12. 此时顶点I已经没有未访问过的邻接顶点了,所以回退到顶点H。
  13. 回退到顶点H后,顶点H也没有未访问过的邻接顶点了,所以继续回退到顶点F。
  14. 回退到顶点F后,顶点F也没有未访问过的邻接顶点了,所以继续回退到顶点E。
  15. 回退到顶点E后,顶点E也没有未访问过的邻接顶点了,所以继续回退到顶点B。
  16. 回退到顶点B后,顶点B也没有未访问过的邻接顶点了,所以继续回退到顶点A。

回退到顶点A后,顶点A也没有未访问过的邻接顶点了,而且顶点A是搜索的起始顶点。至此,整个搜索过程全部结束。由此可见,DFS搜索最终要回退到起始顶点,并且如果起始顶点没有未访问过的邻接顶点了,则算法结束。

在图1(b)中,每个顶点外侧的数字标明了进行深度优先搜索时各顶点访问的次序,称为顶点的深度优先数。图1(b)还给出了访问n个顶点时经过的n-1条边,这n-1条边将n个顶点连接成一棵树,称此图为原图的深度优先生成树,该树的根结点就是深度优先搜索的起始顶点。在图1(b)中,为了更加直观地描述该生成树的树形结构,将此生成树改画成图1(b)中右图所示的树形形状。

DFS算法的实现及复杂度分析

DFS算法的实现

假设有函数DFS(v),可实现从顶点v出发访问它的所有未访问过的邻接顶点。在DFS算法中,必有一数组,设为visited[n],用来存储各顶点的访问状态。如果visited[i]=1,则表示顶点i已经访问过;如果visited[i]=0,则表示顶点i还未访问过。初始时,各顶点的访问状态均为0。

用DFS函数实现可用如图1(a)所示的搜索过程图2表示,在主函数中只要调用DFS(A)就可以搜索整个图。图2中的序号(1)~(16)跟图1(a)中的序号是一一对应的。

如果用邻接表存储图,则DFS算法实现的伪代码如下:

如果用邻接矩阵存储图(设顶点个数为n),则DFS算法实现的伪代码如下:

在上述伪代码中,在递归调用DFS函数前后的两个位置特别重要。

  1. 如果需要在递归搜索前做一些准备工作,则需要在DFS递归调用前的位置写代码。
  2. 如果需要在搜索的回退后做一些还原工作,或者根据搜索结果做一些统计或计算工作,则需要在DFS递归调用后的位置写代码。

算法复杂度分析

现以图1(a)所示的无向图为例分析DFS算法的复杂度。设图中有n个顶点,有m条边。

如果用邻接表存储图,如图3所示,从顶点i进行深度优先搜索,首先要取得顶点i的边链表表头指针,设为p,然后要通过指针p访问它的第1个邻接顶点,如果该邻接顶点未访问过,则从这个顶点出发进行递归搜索;如果这个邻接顶点已经访问过,则指针p要移向下一个边结点。在这个过程中,对每个顶点递归访问1次,即每个顶点的边链表表头指针取出一次,而每个边结点都只访问了一次。由于总共有2m个边结点,所以扫描边的时间为O(2m)。因此,采用邻接表存储图时,进行深度优先搜索的时间复杂性为O(n+2m)。

在图3(b)中,每个边结点上用圆括号括起来的序号表示每条边的扫描顺序。这个扫描顺序不太好理解,现详细解释如下。

  1. 从顶点A出发进行DFS搜索,首先取出顶点A的边链表表头指针,设为pA;pA所指向的边结点表示边(A,B),而顶点B没有访问过,所以要递归调用DFS(B),注意这个过程并没有去扫描边结点(A,B)。
  2. 从顶点B进行DFS搜索,首先取出顶点B的边链表表头指针,设为pB;pB所指向的边结点表示边(B,A),而顶点A已经访问过了,所以将指针pB移向下一个边结点,即要扫描边结点(B,A),并使得pB指向边(B,C)所表示的边结点,所以整个DFS过程最先扫描的边结点是(B,A);现pB指向边结点(B,C),而顶点C还未访问,所以要递归调用DFS(C),同样这个过程并没有去扫描边结点(B,C)。
  3. 从顶点C进行DFS搜索,首先取出顶点C的边链表表头指针,设为pC;pC所指向的边结点表示边(C,B),而顶点B已经访问过了,所以将指针pC移向下一个边结点,即要扫描边结点(C,B)(因此,边结点(C,B)的扫描顺序为2),并使得pB指向边(C,G)所表示的边结点;现pB指向边结点(C,G),而顶点G还未访问,所以要递归调用DFS(G)。
  4. 从顶点G进行DFS搜索,首先取出顶点G的边链表表头指针,设为pG;pG所指向的边结点表示边(G,C),而顶点C已经访问过了,所以要扫描边结点(G,C)(因此,边结点(G,C)的扫描顺序为3),并将指针pG移向下一个边结点,而下一个边结点为空,所以顶点G访问完毕,回退到DFS(C)。
  5. 回退到DFS(C)后,继续扫描边结点(C,G)(因此,边结点(C,G)的扫描顺序为4)后,顶点C也访问完毕,回退到DFS(B)。 ……

如果采用邻接矩阵存储图,由于在邻接矩阵中只是间接地存储了边的信息。在对某个顶点进行DFS搜索时,要检查其他每个顶点,包括它的邻接顶点和非邻接顶点,所需时间为O(n)。例如,在图4(b)中,执行DFS(A)时,要在邻接矩阵中的第0行检查顶点A~I与顶点A是否相邻且是否已经访问过。另外,整个DFS过程,对每个顶点都要递归进行DFS搜索,因此遍历图中所有的顶点所需的时间为O(n^2)。

例题解析

以下通过两道例题的分析,再详细介绍深度优先搜索的算法思想及其实现方法。

例1 骨头的诱惑(Tempter of the Bone)

题目来源:

Zhejiang Provincial Programming Contest 2004, ZOJ2110

题目描述:

一只小狗在一个古老的迷宫里找到一根骨头,当它叼起骨头时,迷宫开始颤抖,它感觉到地面开始下沉。它才明白骨头是一个陷阱,它拼命地试着逃出迷宫。

迷宫是一个N×M大小的长方形,迷宫有一个门。刚开始门是关着的,并且这个门会在第T秒钟开启,门只会开启很短的时间(少于1秒),因此小狗必须恰好在第T秒达到门的位置。每秒钟,它可以向上、下、左或右移动一步到相邻的方格中。但一旦它移动到相邻的方格,这个方格开始下沉,而且会在下1秒消失。所以,它不能在一个方格中停留超过一秒,也不能回到经过的方格。

小狗能成功逃离吗?请帮助它。

输入描述:

输入文件包括多个测试数据。每个测试数据的第1行为3个整数:N、M、T,(1<N、M<7;0<T<50),分别代表迷宫的长和宽,以及迷宫的门会在第T秒时刻开启。

接下来N行信息给出了迷宫的格局,每行有M个字符,这些字符可能为如下值之一。
X:墙壁,小狗不能进入    S:小狗所处的位置
D:迷宫的门         . : 空的方格

输入数据以3个0表示输入数据结束。

输出描述:

对每个测试数据,如果小狗能成功逃离,则输出"YES",否则输出"NO"。

分析:

本题要采用DFS搜索思想求解,本节也借助这道题目详细分析DFS搜索策略的实现方法及搜索时要注意的问题。

  • 搜索策略

以样例输入中的第1个测试数据进行分析,如图5所示。图5(a)表示测试数据及所描绘的迷宫;在图5(b)中,圆圈中的数字表示某个位置的行号和列号,行号和列号均从0开始计起,实线箭头表示搜索前进方向,虚线箭头表示回退方向。

搜索时从小狗所在初始位置S出发进行搜索。每搜索到一个方格位置,对该位置的4个可能方向(要排除边界和墙壁)进行下一步搜索。往前走一步,要将到达的方格设置成墙壁,表示当前搜索过程不能回到经过的方格。一旦前进不了,要回退,要恢复现场(将前面设置的墙壁还原成空的方格),回到上一步时的情形。只要有一个搜索分支到达门的位置并且符合要求,则搜索过程结束。如果所有可能的分支都搜索完毕,还没找到满足题目要求的解,则该迷宫无解。

  • 搜索实现

假设实现搜索的函数为dfs,它带有3个参数。dfs(si,sj,cnt):已经到达(si,sj)位置,且已经花费cnt秒,如果到达门的位置且时间符合要求,则搜索终止;否则继续从其相邻位置继续进行搜索。继续搜索则要递归调用dfs函数,因此dfs是一个递归函数。

成功逃离条件:si=di,sj=dj,cnt=t。其中(di,dj)是门的位置,在第t秒钟开启。

假设按照上、右、下、左顺时针的顺序进行搜索。则对样例输入中的第1个测试数据,其搜索过程及dfs函数的执行过程如图6所示。

在该测试数据中,小狗的起始位置在(0,0)处,门的位置在(2,3)处,门会在第5秒钟开启。在主函数中,调用dfs(0,0,0)搜索迷宫。当递归执行到某一个dfs函数dfs(si,sj,cnt),满足sj==2==di,sj==3==dj,且cnt==5==t,则表示能成功逃离。

图6演示了dfs(0,0,0)的递归执行过程。在图中,各符号含义如下。

  • (0,1)='X':表示往前走一步,要将当前方格设置成墙壁;
  • (0,1)='.':表示回退过程,要恢复现场,即将(0,1)这个位置由原来设置的墙壁还原成空格。

在执行dfs(0,0,0)时,按照搜索顺序,上方是边界,不能走,所以向右走一步,即要递归调用dfs(0,1,1)。在调用dfs(0,1,1)之前,将(0,1)位置置为墙壁。走到(0,1)位置后,下一步要走的位置是(0,2),要递归调用dfs(0,2,2)。在调用dfs(0,2,2)之前,将(0,2)位置置为墙壁。走到(0,2)位置后,下一步要走的位置是(0,3),要递归调用dfs(0,3,3)。在调用dfs(0,3,3)之前,将(0,3)位置置为墙壁。在走到(0,3)位置后,其4个相邻位置中上边、右边是边界,下边是墙壁,左边本来是空的方格,但因为在前面的搜索前进方向上已经将它设置成墙壁了,所以没有位置可走,只能回退到上一层,即dfs(0,3,3)函数执行完毕,要回退到主调函数处,也就是dfs(0,2,2)函数中。

回到dfs(0,2,2)函数处,即处在位置(0,2),且已经走了2秒。(0,2)位置的4个相邻位置中,还有(1,2)这个位置可以走,则从(1,2)位置继续搜索。

按照上述搜索策略,一直搜索到(2,3)位置处,这个位置是门的位置,且刚好走了5秒。所以得出结论:能够成功逃脱。

这里要注意,搜索方向的选择是通过下面的二维数组及循环控制来实现的。该二维数组表示上、右、下、左4个方向相对当前位置x、y坐标的增量。

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
  • 为什么在回退过程中要恢复现场

以样例输入中的第2个测试数据来解释这个问题。在这个测试数据中,如果加上回退过程的恢复现场操作,则不管按什么顺序(上、右、下、左顺序或者左、右、下、上顺序)进行搜索,都能成功脱离;但是去掉回退过程的恢复现场操作后,按某种搜索顺序能成功脱离,但按另外一种搜索顺序则不能成功脱离,这是错误的。图7~图10以测试数据2为例分析了加上和去掉回退过程分别按两种搜索顺序进行搜索的过程和结果。

测试数据2分析1:回退过程有恢复现场,dir数组如下,即搜索方向为上、右、下、左顺序,整个搜索过程如图7(b)所示,dfs函数的执行过程如图7(c)所示。dfs函数执行的结果是能成功逃脱。

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

测试数据2分析2:回退过程有恢复现场,dir数组如下,即搜索方向为左、右、下、上顺序,整个搜索过程如图8(b)所示,dfs函数的执行过程如图8(c)所示。从图8(b)和图8(c)可知,往左搜索走不通后,此时右边(即(1,3)位置)仍为'.'(在回退的时候恢复了),从这个位置出发再进行搜索,将找到一条能成功逃脱的路径。因此,dfs函数执行的结果是能成功逃脱。

int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};

测试数据2分析3:去掉回退过程的恢复现场操作,在图9(c)中,“(1,3)='.';”等代码加上了删除线。dir数组如下,即搜索方向为上、右、下、左顺序,整个搜索过程如图9(b)所示,dfs函数的执行过程如图9(c)所示。dfs函数执行的结果是能成功逃脱。

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

测试数据2分析4:去掉回退过程的恢复现场操作,在图10(c)中,“(0,2)='.';”等代码加上了删除线。dir数组如下,即搜索方向为左、右、下、上顺序,整个搜索过程如图10(b)所示,dfs函数的执行过程如图10(c)所示。由于没有恢复现场操作,在往左搜索走不通后,所有位置都被设置为墙壁,无法再进行搜索了,如图10(d)所示。因此,dfs函数执行的结果是不能成功逃脱。

int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};

为什么在回退过程中恢复现场?答案是:如果当前搜索方向行不通,该搜索过程要结束了,但并不代表其他搜索方向也行不通,所以在回退时必须还原到原来的状态,保证其他搜索过程不受影响。

代码如下:

备注:

  1. 用C语言的scanf函数读入字符型数据(使用"%c"格式控制)时,会把上一行的换行符(ASCII编码值为10)读进来。因此在读入每一行迷宫字符前,要跳过上一行的换行符。
  2. 本程序两处地方使用了剪枝,分别是搜索前的剪枝和搜索过程中的剪枝,详见程序中的注释。而所谓剪枝,顾名思义,就是通过某种判断,避免一些不必要的搜索过程。形象地说,就是剪去了搜索过程中的某些“枝条”,故称剪枝。

例2 油田(Oil Deposits)

题目来源:

Mid-Central USA 1997, ZOJ1709, POJ1562

题目描述:

GeoSurvComp地质探测公司负责探测地下油田。每次GeoSurvComp公司都是在一块长方形的土地上来探测油田。在探测时,他们把这块土地用网格分成若干个小方块,然后逐个分析每块土地,用探测设备探测地下是否有油田。方块土地底下有油田则称为pocket,如果两个pocket相邻,则认为是同一块油田,油田可能覆盖多个pocket。试计算长方形的土地上有多少个不同的油田。

输入描述:

输入文件中包含多个测试数据,每个测试数据描述了一个网格。每个网格数据的第1行为两个整数:m、n,分别表示网格的行和列;如果m=0,则表示输入结束,否则1≤m≤100,1≤n≤100。接下来有m行数据,每行数据有n个字符(不包括行结束符)。每个字符代表一个小方块,如果为“*”,则代表没有石油,如果为“@”,则代表有石油,是一个pocket。

输出描述:

对输入文件中的每个网格,输出网格中不同的油田数目。如果两块不同的pocket在水平、垂直或者对角线方向上相邻,则被认为属于同一块油田。每块油田所包含的pocket数目不会超过100。

分析:

从网格中某个“@”字符位置开始进行DFS搜索,可以搜索到跟该“@”字符位置同属一块油田的所有“@”字符位置。为避免重复搜索,可以在搜索的前进方向,将每个“@”字符位置替换成“*”字符。这样,从网格中每个“@”字符位置进行搜索,可以得到油田的数目。

在程序实现时,可以用下面的二维数组表示(x,y)位置的8个相邻方向,该二维数组依次表示左上、上、右上、右、右下、下、左下、左8个方向(顺时针顺序)相对(x,y)位置的x、y坐标增量。

int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};

另外,与例1中使用scanf函数(采用"%c"格式控制)读取迷宫中的字符时需要跳过上一行的换行符不同的是,在本题中,读入网格中的每行字符时,采用"%s"格式控制,这种输入方式会自动跳过每行末尾的换行符,所以不需要专门用调用scanf函数来读取换行符。

代码如下:

参考文档