图的深度优先搜索算法并生成DFS树

ゝ一世哀愁。 2022-06-04 04:05 185阅读 0赞

前面一篇文章介绍了[图的广度优先搜索算法和BFS树][BFS]，这篇文件笔者将介绍另一种图的遍历算法-深度优先算法

#### 概述 ####

深度优先搜索（Depth-First Search，DFS）选取下一顶点的策略，可概括为：**优先选取最后一个被访问到的顶点的邻居。**以顶点 s 为基点的 DFS 搜索，将首先访问顶点 s；再从 s 所有尚未访问到的邻居中任取其一，并以之为基点，递归地执行 DFS 搜索。故各顶点被访问到的次序，类似于树的先序遍历而各顶点被访问完毕的次序，则类似于树的后序遍历

#### 图的深度优先搜索的代码实现 ####

首先来看看再遍历算法中节点和弧使用到的属性：

**节点**

private int status = 0;  //状态 0 undiscovered "未发现"  1 discovered "已发现"  2 visited "已完成"
        private int parent = -1;
        private int dTime = -1; //开始遍历的时间
        private int fTime = -1; //结束遍历的时间

**弧**

private int type;
        //弧类型：0 CROSS 跨边  1 TREE（支撑树） 
        //2 BACKWARD(该弧的起点和终点在支撑树中存在终点到起点的路径) 
        //3 FORWARD (该弧的起点和终点在支撑树中存在其他路径依然可以从起点到终点)

**遍历算法**

//从节点index开始遍历
       public void dfsTree(int index) {
          this.reload(); //复位所有节点和弧状态
          //用来记录某个节点被遍历的时间
          Integer clock = new Integer(0);
          int s = index;
          do {
              if(allNodes[s].getStatus() == 0){
                  dfs(s, clock);
              }
          }while(index !=(s = (++s%size)));//按序号检查，防止遗漏index无法连通的节点
        }
    
        public void dfs(int index, Integer clock) {
          //发现该节点
          allNodes[index].setStatus(1);
          //记录开始访问的时间
          allNodes[index].setdTime(++clock);
          //找出节点index的所有邻居
          for(int i=0; i<size; i++) {
              Edge edge = getEdge(index, i);
              if(getEdge(index, i)!=null) {
                  switch(allNodes[i].getStatus()) {
                  //如果节点i尚未被发现
                  case 0:
                      //并设置支撑树(index为i的parent)
                      allNodes[i].setParent(index);
                      //发现该节点
                      edge.setType(1);
                      //开始递归
                      dfs(i, clock);
                      break;
                  //如果节点i已被访问但没有完全被访问，则i为i->parent->parent... == index
                  case 1:
                      edge.setType(2);
                      break;
                 //如果该节点已经被访问完毕。则根据其遍历结束时间来区分
                  case 2:
                      int type = allNodes[index].getdTime() > allNodes[i].getdTime() ? 0: 3;
                      edge.setType(type);
                      break;
                  }
    
              }
          }
          //index节点访问完毕
          allNodes[index].setStatus(2);
          allNodes[index].setfTime(++clock);
        }

算法的实质功能，由子算法 dfs（）递归地完成。每一递归实例中，都先将当前节点 v 标记为 “已发现” 状态，再逐一核对其各邻居 u 的状态并做相应处理。待其所有邻居均已处理完毕之后，将顶点 v 置为 “访问完毕” 状态，便可递归回溯。

若项点 u 尚处于 “未发现” 状态，则将边（v, u）归类为树边，并将v置为u的parent。此后，便可将u作为当前顶点，继续递归地遍历。

若项点 u 处于 “已发现 ” 状态，则意味着在此处发现一个有向环路。此时，在 DFS 遍历树中 u 必为 v 的祖先，故应将边（v, u）归类为后向边BACKWARD。

这里为每个顶点 v 都记录了被发现的和访问完成的时刻，对应的时间区间【dTime (v), fTime (v）】均称作 v 的活跃期（active duration）。实际上，任意顶点 v 和 u 之间是否存在祖先 /后代的“血缘”关系，完全取决于二者的活跃期是否相互包含。

对于有向图，顶点 u 还可能处于 “已发现” 状态。此时，只要比对 v 与 u 的活跃期，即可判定在DFS 树中 v 是否为 u 的祖先。若是，则边（v, u）应归类为前向边FORWARD（forward edge）；否则，二者必然来自相互独立的两个分支，边（v, u）应归类为跨边（cross edge）。**如果v的dTime()小则为前向边，否则为跨边**

bfs (s）返回后，所有访问过的顶点通过 parent指针依次联接，从整体上给出了顶点 s 所属连通或可达分量的一棵遍历树，称作深度优先搜索树或 DFS 树（DFS tree）。与 BFS 搜索一样，此时若还有其它的连通或可达分量，则可以其中任何顶点为基点，再次启动 DFS 搜索，来构成了 DFS 森林（DFS forest）。

#### 实例 ####

下图针对含 7 个顶点和 18 条边的某有向图，给出了 DFS 搜索的详细过程。注意观察顶点时间标签的设置，顶点状态的演变，边的分类和结果，以及 DFS 树（森林）的生长过程：

![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]

**粗边框白色，为当前顶点；细边框白色、双边框白色和黑色，分别为处于未发现、已发现和已完成状态的顶点；dTime和fTime标签，分别标注与各顶点的左右**

最终结果如图t所示，为包含两棵DFS树的一个DFS森林。可以看出，选用不同的起始基点，生成的DFS树（森林）也可能各异。如本例中，若从D开始搜索，则DFS森林可能如图u所示。

#### 复杂度 ####

除了原图本身，深度优先搜索算法所使用的空间，主要消耗于各顶点的时间标签和状态标记，以及各边的分类标记，二者累计不超过 0 (n) + O (e) = O (n + e）。当然，如采用以上代码的直接递归实现方式，操作系统为维护运行栈还需耗费一定量的空间一尽管这部分增量在渐进意义下还不足以动摇以上结论。

时间方面，不计对子函数 dfs（）的调用，dfsTree（）本身对所有顶点的枚举共需 0 (n）时间。不计 dfs（）之间相互的递归调用，每个顶点、每条边只在子函数 dfs（）的某一递归实例中耗费 O (1）时间，故累计亦不过 0 (n + e）时间。综合而言，深度优先搜索算法也可在 O (n + e）时间内完成。

[BFS]: http://blog.csdn.net/canot/article/details/78705621
[SouthEast]: /images/20220604/d2fbd124c4464e3eb48d5aa4884a9eb1.png
[SouthEast 1]: /images/20220604/bd262f0ca40c4e899e898138db8b61e4.png
[SouthEast 2]: /images/20220604/82658094e8a147c7a4a371822862df53.png
[SouthEast 3]: /images/20220604/a9a07d027ff24d33bcd2ba6d0f8e5b13.png
[SouthEast 4]: /images/20220604/7380e41c7f134227a10b8079ee01164a.png
[SouthEast 5]: /images/20220604/9c8c7546fc3c4ea687338e957ef02af3.png
[SouthEast 6]: /images/20220604/65b812d29c3549bbbb71dc1383a00fca.png