【数据结构与算法】深度优先搜索（DFS）

本文主要是介绍【数据结构与算法】深度优先搜索（DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

深度优先搜索（DFS）

对于考研人来说，BFS和DFS指的是图的两种遍历算法。

但是严格意义上说，BFS和DFS是两种搜索策略。

• BFS代表算法在执行时，会像树的层次遍历那样，从属于同一个结点的后继的访问顺序相邻。

• DFS代表算法在执行时，会像树的先序遍历那样，沿着某条路径走到终点，再返回走另外一条路径。

基本思路

DFS的实现思路如下：

1. 访问起始结点v。
2. 从起始结点v出发，访问v的任意一个未被访问的邻接结点w1，再访问w1的任意一个未被访问邻接结点w2，再访问w2的任意一个未被访问的邻接结点w3…以此类推，直至无法继续向下访问。
3. 当无法继续向下访问时，回到最近被访问的顶点，若它存在邻接结点未被访问过，则以该结点作为起始结点执行操作2。
4. 重复2-3直至所有顶点都被访问。

例如，现在有一个有向图：

那么按照DFS的思路：

假设从1开始搜索，那么先访问 1。

再执行步骤2，可以得到序列 2 -> 3。此时3无法继续访问。

再执行步骤3，返回到2，但是2无邻接结点未被访问，返回到1，1有一个邻接结点4，执行步骤2，得到序列 4。

综上，按照DFS得到的搜索序列为 1 2 3 4。

基本实现

DFS这种访问，然后回退的方式，非常地契合递归原理。因此DFS常常使用递归实现。（非递归方式可以借助栈来实现，但是递归方式本质上也是一个栈）

这里我们基于邻接矩阵实现DFS，如果有感兴趣的同学，可以实现一下基于邻接表的DFS算法。

const int MAX_SIZE = 100; // 最大容量struct Graph
{VT vex[MAX_SIZE];             // 顶点集int edge[MAX_SIZE][MAX_SIZE]; // 边集int v_num; // 当前顶点个数
};bool visited[MAX_SIZE];/*** 访问结点*/
void visit(int i)
{// 标记已被访问visited[i] = true;// ... 访问动作
}/*** DFS的递归实现* * 执行DFS前需要先初始化visited[]。* 按照深度优先的顺序遍历所有与i连通的结点。* * @param {Graph} G 图* @param {int} i 起始顶点*/
void DFS(Graph G, int i)
{visit(i);for (int j = 0; j < G.v_num; j++){if (G.edge[i][j] == 1 && visited[j] == false){DFS(G, j);}}
}

DFS的应用

判断图的连通性

对于无向图来说，若图是连通的，那么从任意一个结点出发，执行一遍BFS搜索即可访问到图中的所有结点。

对于有向图来说，若图是强连通的，那么和无向图一样，从任意一个结点出发，执行一遍DFS也能够访问到图中的所有结点。

因此DFS可以用来判断图的连通性，从任意一个结点出发执行一遍DFS，统计访问到的结点个数，与图中所有结点的个数进行比较，即可实现判断。

图的遍历

由于并不是所有的图都是连通图，因此，在BFS的基础上，我们还需要保证图中的每一个结点都被访问到。

因此，我们还需要添加一个操作，来实现遍历图中的每一个结点：

1. 访问起始结点v。
2. 从起始结点v出发，访问v的任意一个未被访问的邻接结点w1，再访问w1的任意一个未被访问邻接结点w2，再访问w2的任意一个未被访问的邻接结点w3…以此类推，直至无法继续向下访问。
3. 当无法继续向下访问时，回到最近被访问的顶点，若它存在邻接结点未被访问过，则以该结点作为起始结点执行操作2。
4. 重复2-3直至所有顶点都被访问。
5. 从剩余未被访问的结点中任选一个结点，执行操作1到4，直至所有结点都被访问。

// C++void DFSTraverse(Graph G){// 初始化for (int j = 0; j < G.v_num; j++){visited[j] = false;}for(int i=0; i<G.v_num; i++){if(visited[i]) DFS(G, i);}
}void DFS(Graph G, int i)
{visit(i);for (int j = 0; j < G.v_num; j++){if (G.edge[i][j] == 1 && visited[j] == false){DFS(G, j);}}
}

暴力枚举

根据DFS的思路，算法在执行的时候实际上就是在尝试每一种可能的情况。因此DFS又叫暴力搜索算法。它能够解决一些形如排列组合之类的需要枚举所有情况的问题。

代码的大致格式如下：

void dfs(int step)
{判断是否符合条件{相应操作}枚举每一种可能{标记 //防止多次重复枚举同一个方案继续下一步dfs(step+1)恢复初始状态 //恢复现场}
}

判断图中是否有环（回路）

按照DFS的规则，一个结点在访问完其所有相邻节点之后，会从当前结点的父节点回溯到下一个未被访问的相邻结点。如果一个结点已经被访问过，那么它应该已经在集合中，等待回溯。但是，如果这个结点再次被访问，就说明存在一个路径可以从这个结点直接回溯到其父结点，形成一个回路。

所以我们可以通过DFS来判断图中是否存在回路。

全篇结束，感谢阅读！

这篇关于【数据结构与算法】深度优先搜索（DFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---