算法学习笔记：6.深度优先搜索算法——从原理到实战，涵盖 LeetCode 与考研 408 例题

在计算机科学领域，搜索算法是解决问题的重要工具，其中深度优先搜索（Depth-First Search，简称 DFS）凭借其简洁高效的特性，在图论、回溯、拓扑排序等众多场景中发挥着关键作用。无论是 LeetCode 算法题，还是考研计算机专业基础综合（408）考试，深度优先搜索都是高频考点。

深度优先搜索算法核心思路

深度优先搜索的基本思想是沿着一条路径尽可能深地探索，直到无法继续或达到目标状态，然后回溯到上一个节点，继续探索其他路径，直至遍历完所有可达节点。在图结构或树结构中，DFS 可以用来遍历所有节点、寻找路径、检测连通性等。

1.1 算法实现方式

DFS 通常有两种实现方式：递归和迭代（借助栈数据结构）。

• 递归实现：利用函数调用栈，从起始节点开始，不断递归访问相邻节点，当达到边界条件（如访问过的节点、无相邻节点）时回溯。代码简洁直观，但可能因递归深度过深导致栈溢出。

• 迭代实现：手动维护一个栈，将起始节点入栈，每次取出栈顶节点，访问其未访问过的相邻节点并将其入栈，直到栈为空。这种方式可避免栈溢出问题，适用于大规模数据。

1.2 算法流程

以图结构为例，DFS 的基本流程如下：

1. 选择一个起始节点，标记为已访问。

1. 从起始节点出发，找到一个未访问的相邻节点，将其标记为已访问，并以该节点为新的起始节点，递归执行步骤 2。

1. 当当前节点的所有相邻节点都已访问时，回溯到上一个节点，继续执行步骤 2。

1. 重复步骤 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 与其他算法的结合应用，探索其在更复杂场景下的优化与拓展。

希望本文能够帮助读者更深入地理解深度优先搜索算法，并在实际项目中发挥其优势。谢谢阅读！

---

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。