在计算机科学领域，搜索算法是解决问题的重要工具，其中深度优先搜索（Depth-First Search，简称 DFS）凭借其简洁高效的特性，在图论、回溯、拓扑排序等众多场景中发挥着关键作用。无论是 LeetCode 算法题，还是考研计算机专业基础综合（408）考试，深度优先搜索都是高频考点。
深度优先搜索算法核心思路
深度优先搜索的基本思想是沿着一条路径尽可能深地探索，直到无法继续或达到目标状态，然后回溯到上一个节点，继续探索其他路径，直至遍历完所有可达节点。在图结构或树结构中，DFS 可以用来遍历所有节点、寻找路径、检测连通性等。
1.1 算法实现方式
DFS 通常有两种实现方式：递归和迭代（借助栈数据结构）。
- 递归实现：利用函数调用栈，从起始节点开始，不断递归访问相邻节点，当达到边界条件（如访问过的节点、无相邻节点）时回溯。代码简洁直观，但可能因递归深度过深导致栈溢出。
- 迭代实现：手动维护一个栈，将起始节点入栈，每次取出栈顶节点，访问其未访问过的相邻节点并将其入栈，直到栈为空。这种方式可避免栈溢出问题，适用于大规模数据。
1.2 算法流程
以图结构为例，DFS 的基本流程如下：
- 选择一个起始节点，标记为已访问。
- 从起始节点出发，找到一个未访问的相邻节点，将其标记为已访问，并以该节点为新的起始节点，递归执行步骤 2。
- 当当前节点的所有相邻节点都已访问时，回溯到上一个节点，继续执行步骤 2。
- 重复步骤 2 和 3，直到所有可达节点都被访问。
绘制出的 DFS 递归实现的流程图：
为了更直观地理解，假设我们有如下无向图：
从节点 A 开始进行 DFS，访问顺序可能为 A -> B -> D -> E -> C（顺序不唯一，取决于具体实现）。
LeetCode 例题实战
例题 1：200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
解题思路：使用 DFS 遍历二维网格，当遇到'1'时，将其及其相邻的'1'全部标记为已访问（可以将'1'改为'0'），每完成一次 DFS，岛屿数量加 1。
public class NumIslands {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}例题 2：79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
解题思路：从网格中的每个单元格开始进行 DFS，当当前字符与单词当前字符匹配时，继续向相邻单元格递归搜索。为避免重复访问，使用一个布尔数组记录单元格是否已被访问。如果找到匹配的路径，返回true；遍历完所有单元格仍未找到，则返回false。
public class WordSearch {
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(board, word, 0, i, j, visited)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int i, int j, boolean[][] visited) {
int m = board.length;
int n = board[0].length;
if (index == word.length()) {
return true;
}
if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] != word.charAt(index)) {
return false;
}
visited[i][j] = true;
boolean result = dfs(board, word, index + 1, i - 1, j, visited) ||
dfs(board, word, index + 1, i + 1, j, visited) ||
dfs(board, word, index + 1, i, j - 1, visited) ||
dfs(board, word, index + 1, i, j + 1, visited);
visited[i][j] = false;
return result;
}
}考研 408 例题分析
例题：已知一个无向连通图的邻接表存储结构，编写算法判断图中是否存在回路。
解题思路：利用 DFS 遍历图，在遍历过程中记录每个节点的前驱节点。当访问到一个已访问过的节点，且该节点不是当前节点的前驱节点时，说明存在回路。
import java.util.ArrayList;
import java.util.List;
class Graph {
int V;
List<List<Integer>> adj;
Graph(int v) {
V = v;
adj = new ArrayList<>(v);
for (int i = 0; i < v; i++) {
adj.add(new ArrayList<>());
}
}
void addEdge(int v, int w) {
adj.get(v).add(w);
adj.get(w).add(v);
}
boolean isCyclic() {
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(i, -1, visited)) {
return true;
}
}
}
return false;
}
private boolean dfs(int v, int parent, boolean[] visited) {
visited[v] = true;
for (int i : adj.get(v)) {
if (!visited[i]) {
if (dfs(i, v, visited)) {
return true;
}
} else if (i != parent) {
return true;
}
}
return false;
}
}
public class CyclicGraph {
public static void main(String[] args) {
Graph g1 = new Graph(5);
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);
if (g1.isCyclic()) {
System.out.println("Graph contains cycle");
} else {
System.out.println("Graph does not contain cycle");
}
Graph g2 = new Graph(3);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
if (g2.isCyclic()) {
System.out.println("Graph contains cycle");
} else {
System.out.println("Graph does not contain cycle");
}
}
}总结
深度优先搜索算法以其独特的搜索策略，在解决各类问题中展现出强大的能力。通过 LeetCode 例题和考研 408 真题的实战演练，我们不仅掌握了 DFS 在不同场景下的应用，还熟悉了其 Java 代码实现。在实际编程和考研备考中，熟练运用 DFS 算法，能够有效提升问题解决能力。后续可以进一步研究 DFS 与其他算法的结合应用，探索其在更复杂场景下的优化与拓展。
希望本文能够帮助读者更深入地理解深度优先搜索算法，并在实际项目中发挥其优势。谢谢阅读！
希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。
