14. 深度优先搜索（DFS）
大约 4 分钟
深度优先搜索（DFS）原理
深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。该算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
优缺点
优点：
- 空间复杂度较低：相比广度优先搜索（BFS），DFS通常只需要较少的内存空间，因为它不需要存储所有待访问的节点。
- 代码实现简单：DFS的递归实现通常比BFS的迭代实现更为直观和简洁。
缺点：
- 时间复杂度可能较高：对于某些图，DFS可能需要更长的时间才能访问所有节点，因为它会深入搜索一个分支直到无法继续，然后再回溯。
- 不适用于寻找最短路径：DFS通常不会找到从源点到目标点的最短路径，因为它不是基于距离的搜索。
使用场景
- 图的连通性问题：DFS可以用来判断图是否连通，或者找出图中的所有连通分量。
- 拓扑排序：在有向无环图（DAG）中，DFS可以用来进行拓扑排序。
- 寻找强连通分量：在有向图中，DFS可以用来找出所有的强连通分量。
- 解决迷宫问题：在迷宫问题中，DFS可以用来搜索所有可能的路径，找到从起点到终点的路径。
- 搜索问题：DFS也可以用于各种搜索问题，如树的搜索、图的搜索等。
常用算法
虽然DFS本身是一个算法，但有一些基于DFS的常用算法和变体：
- 回溯算法：回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些更改来丢弃该解，即“回溯”并尝试其他可能的解。回溯算法通常使用DFS来实现。
- 图的着色问题：在图的m着色问题中，需要给图的每个顶点分配一种颜色，使得相邻的顶点颜色不同。这个问题可以使用DFS和回溯算法来解决。
- 旅行商问题（TSP）的近似解：虽然TSP是一个NP-hard问题，但DFS可以用于找到其近似解或某些特定情况下的解。
- 八数码问题（滑动拼图）：这是一个经典的搜索问题，目标是将一个乱序的3x3数字拼图滑动到正确的位置。DFS可以用来搜索所有可能的移动序列。
- 求解迷宫问题：在迷宫问题中，DFS可以用来搜索所有可能的路径，找到从起点到终点的路径。这通常与回溯算法结合使用，以便在发现死路时能够回溯并尝试其他路径。
Java代码示例
以下是使用Java语言编写的深度优先搜索（DFS）的示例代码，该代码适用于无向图：
首先，我们需要定义一个表示图的类，这里我们使用邻接列表来表示图：
import java.util.*;
class Graph {
private int V; // 顶点数量
private LinkedList<Integer> adj[]; // 邻接列表
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
// 因为是无向图，所以也要添加反向边
adj[w].add(v);
}
// DFS遍历
void DFS(int v, boolean visited[]) {
// 标记当前节点为已访问
visited[v] = true;
System.out.print(v+" ");
// 递归访问所有未访问的邻居节点
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFS(n, visited);
}
}
// DFS遍历的入口函数
void DFS(int v) {
boolean visited[] = new boolean[V];
// 调用递归函数进行DFS遍历
DFS(v, visited);
}
}
// 主类
public class Main {
public static void main(String args[]) {
// 创建一个图，包含5个顶点
Graph g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
System.out.println("Depth First Traversal (starting from vertex 0):");
// 从顶点0开始进行DFS遍历
g.DFS(0);
}
}在上面的代码中，Graph 类用于表示一个图，并且实现了 addEdge 方法来添加边和 DFS 方法来进行深度优先搜索。主函数 main 中创建了一个 Graph 对象并添加了边，然后调用 DFS 方法从顶点0开始进行深度优先遍历。
运行上述代码，你将看到从顶点0开始的深度优先遍历结果。在这个例子中，输出将是 0 1 4 3 2（遍历的顺序可能因具体实现和图的结构而有所不同，但会访问所有节点一次）。