在之前的文章中，我们已经了解了图的表示方式。现在，让我们来探讨一种用于遍历和搜索树或图数据结构的重要算法——深度优先搜索（DFS）。
DFS 算法简介
深度优先搜索（DFS）是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始（在图的情况下，选择任意一个节点作为根节点），并在回溯之前尽可能沿着每个分支进行深入探索。
我们可以把 DFS 想象成走迷宫的策略：只要没遇到死胡同，我们就一直沿着一条路往前走；一旦走不通了，我们就退回到最近的路口，尝试另一条没走过的路。这就是“深度优先”的直观含义。
#### 图的遍历：DFS vs BFS
深度优先搜索 (DFS) 和广度优先搜索 (BFS) 是图论中两种最基本的遍历算法。
- BFS (广度优先搜索)：像水波纹一样，从起点开始，先访问所有距离最近的邻居节点，然后再访问距离稍远一点的节点。它通常使用队列 数据结构来实现。
- DFS (深度优先搜索)：像前面提到的走迷宫，一条路走到黑，直到无路可走再返回。它通常使用递归 或栈 数据结构来实现。
#### 算法核心思路
DFS 的核心思想在于：
- 访问当前节点：首先处理当前的起始节点（标记为已访问）。
- 递归探索邻居：遍历当前节点的所有邻接节点。对于每一个邻接节点，如果它尚未被访问过，我们就对它递归执行 DFS 操作。这意味着我们会深入到该邻居节点的分支中去，直到该分支结束，才会回来继续处理当前节点的其他邻居。
这种策略保证了我们沿着图的某一条路径尽可能深地探索，直到遇到未访问过的节点或到达了终点。
算法流程图解
让我们通过一个简单的无向图示例来看看 DFS 是如何工作的。
#### 步骤演示：
我们以节点 0 为起点。
- 起始：从节点 0 开始。将其标记为已访问，并打印出来。接着，我们查看 0 的邻居节点。假设邻接表中顺序为 1, 2。
- 深入节点 1：我们发现邻居节点 1 未被访问。于是我们从 0 移动到 1。将 1 标记为已访问并打印。现在我们查看 1 的邻居（0, 2）。
- 回溯与发现新路径：
* 节点 1 的邻居是 0 和 2。节点 0 已经被访问过了。
* 我们发现邻居节点 2 未被访问。于是我们移动到 2。将 2 标记为已访问并打印。
- 继续深入节点 3：现在我们处于节点 2。查看它的邻居（1, 3）。
* 节点 1 已被访问。
* 节点 3 未被访问。我们移动到 3。将 3 标记为已访问并打印。
- 到达死胡同并回溯：现在我们处于节点 3。查看它的邻居（2, 4）。
* 节点 2 已被访问。
* 节点 4 未被访问。我们移动到 4。将 4 标记为已访问并打印。
- 最终回溯：现在我们处于节点 4。它的唯一邻居是 3，且已被访问。没有未访问的邻居了，我们开始回溯：
* 从 4 回溯到 3。
* 从 3 回溯到 2。
* 从 2 回溯到 1。
* 从 1 回溯到 0。
* 此时回到了起点 0，且 0 的所有邻居都已访问。遍历结束。
最终输出结果：
0 1 2 3 4
> 注意：图的 DFS 遍历结果取决于我们在邻接表中存储邻居节点的顺序。上面的过程假设了特定的邻接表顺序。在实际代码中，我们可以通过调整入栈或递归的顺序来改变遍历结果。
代码实现
在实现中，为了处理那些可能包含环的图（即不仅限于树结构），我们必须使用一个被访问数组（或哈希集合）来记录那些已经被处理过的节点，防止算法陷入死循环。
下面是基于上述图结构的代码实现示例。
#### 方法 1：递归实现
递归是实现 DFS 最直观的方式。函数调用栈会自动保存我们的回溯路径。
// C++ 代码示例
#include
using namespace std;
// 图的类定义
class Graph {
int V; // 顶点数
// 邻接表
list *adj;
// 一个辅助递归函数，被 DFS() 使用
void DFSUtil(int v, bool visited[]);
public:
// 构造函数
Graph(int V);
// 添加边到图
void addEdge(int v, int w);
// DFS 遍历
// 从 v 开始访问被访问数组中可到达的顶点
void DFS(int v);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // 将 w 添加到 v 的列表
}
void Graph::DFSUtil(int v, bool visited[])
{
// 标记当前节点为已访问并打印
visited[v] = true;
cout << v << " ";
// 递归访问所有相邻顶点
for (auto i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// 从 v 开始的 DFS 遍历
void Graph::DFS(int v)
{
// 将所有顶点初始化为未访问
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// 调用递归辅助函数
DFSUtil(v, visited);
}
// Driver 代码
int main()
{
// 创建上面图示中的图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 4);
cout << "Following is Depth First Traversal"
" (starting from vertex 2)
";
// Function call
g.DFS(2);
return 0;
}
#### 方法 2：迭代实现
如果不使用递归，我们可以使用显式的栈 数据结构来模拟递归过程。
// C++ 迭代 DFS 代码示例
#include
#include
#include
using namespace std;
// 图的类定义
class Graph {
int V; // 顶点数
vector<vector> adj; // 邻接表
public:
Graph(int V) : V(V), adj(V) {}
// 添加无向边
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v); // 因为是无向图
}
// 从 v 开始的迭代 DFS 遍历
void DFS(int start) {
// 被访问数组
vector visited(V, false);
stack stack;
// 将当前节点压入栈并标记为已访问
stack.push(start);
visited[start] = true;
while (!stack.empty()) {
// 弹出一个顶点并打印
int curr = stack.top();
stack.pop();
cout << curr <= 0; i--) {
int adjNode = adj[curr][i];
if (!visited[adjNode]) {
visited[adjNode] = true;
stack.push(adjNode);
}
}
}
}
};
// Driver 代码
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 4);
cout << "Following is Depth First Traversal (starting from vertex 2):
";
g.DFS(2);
return 0;
}
复杂度分析
让我们分析一下 DFS 算法的复杂度，设 $V$ 为图中的顶点数，$E$ 为边数。
- 时间复杂度：$O(V + E)$
* 这是因为对于每个顶点，我们只访问一次（$O(V)$）。
* 对于每个顶点，我们遍历其所有邻接边。在所有顶点的遍历中，每条边总共被处理两次（对于无向图，从两个端点各处理一次；对于有向图，处理一次）。所以边处理的总时间是 $O(E)$。
* 总体时间复杂度是线性的，即 $O(V + E)$。
- 空间复杂度：$O(V)$
* 除了存储图的邻接表外，我们需要额外的空间来存储 被访问数组，大小为 $O(V)$。
* 如果使用递归，还需要考虑递归调用栈的显式或隐式开销，在最坏情况下（线性链式图），栈的深度可能达到 $O(V)$。
应用场景
DFS 是一个非常强大的算法，它在许多实际问题中都有应用，例如：
- 检测图中的环：如果我们探索到一个已经访问过的节点（且不是父节点），则说明图中存在环。
- 路径查找：用于查找两个节点之间是否存在路径，或者找出所有可能的路径。
- 拓扑排序：用于有向无环图 (DAG) 的线性排序，常用于任务调度问题。
- 查找强连通分量：例如 Kosaraju 算法。
- 求解迷宫问题：正如我们前面比喻的那样，DFS 非常适合在迷宫中寻找出口。
- 生成树：DFS 可以用来生成图的深度优先搜索生成树/森林。