深度优先与广度优先搜索:从栈与队列的选择到最短路径的博弈

给定一个迷宫，从入口到出口有多条路径。你应该选择哪种策略？一种方式是沿着每条路一直走到底，走不通就返回上一个分叉口换条路——这就是深度优先搜索。另一种方式是先探索所有离入口距离为1的格子，再探索距离为2的格子，层层推进——这就是广度优先搜索。

这两种策略代表了两种根本不同的思维方式：一种追求纵深，一种追求广度。在算法的世界里，它们演化成了DFS和BFS，成为图论和树遍历的两大基石。

栈与队列：两种数据结构的哲学分野

深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）的核心区别在于数据结构的选择：DFS使用栈（Stack），BFS使用队列（Queue）。这个选择看似简单，却决定了两种算法完全不同的行为模式。

栈遵循后进先出（LIFO）原则。当DFS遍历到某个节点时，它会将该节点的所有邻居压入栈中，然后弹出栈顶元素继续探索。这意味着最后被发现的节点会被最先探索，形成一条不断向下延伸的路径，直到无路可走才回溯。

队列遵循先进先出（FIFO）原则。当BFS遍历到某个节点时，它会将该节点的所有邻居加入队列尾部，然后从队列头部取出节点继续探索。这意味着最先被发现的节点会被最先探索，形成层层推进的波纹状遍历模式。

sequenceDiagram
    participant S as 栈
    participant DFS as DFS遍历
    Note over S,DFS: DFS: 后进先出 (LIFO)
    S->>DFS: 弹出栈顶 (最后加入的)
    DFS->>S: 压入邻居 (新的成为栈顶)
    
    participant Q as 队列
    participant BFS as BFS遍历  
    Note over Q,BFS: BFS: 先进先出 (FIFO)
    Q->>BFS: 取出队首 (最早加入的)
    BFS->>Q: 加入邻居 (放在队尾)

DFS：一条路走到黑

DFS的核心思想非常直观：从起点出发，沿着一条路径尽可能深入，直到无法继续前进，然后回溯到上一个分叉点，选择另一条路径继续探索。这个过程可以自然地用递归实现，也可以显式地使用栈来模拟。

递归实现：代码最简洁的形式

递归是DFS最自然的实现方式。每次递归调用代表"沿着当前路径继续前进"，递归返回代表"回溯到上一个节点"。

// DFS递归遍历图
public void dfsRecursive(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    // 处理当前节点
    System.out.print(node + " ");
    
    // 遍历所有邻居
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfsRecursive(neighbor, visited, graph);
        }
    }
}

递归实现的优势在于代码简洁直观，但需要注意递归深度问题。对于深度很大的图（比如一条链），可能导致栈溢出。

迭代实现：显式栈的运用

迭代实现通过显式地使用栈来模拟递归过程，避免了递归深度限制的问题。

// DFS迭代遍历图
public void dfsIterative(int start, List<List<Integer>> graph) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;
        
        visited[node] = true;
        System.out.print(node + " ");
        
        // 逆序添加邻居以保证遍历顺序与递归一致
        for (int i = graph.get(node).size() - 1; i >= 0; i--) {
            int neighbor = graph.get(node).get(i);
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

二叉树的三种DFS遍历

对于二叉树，DFS可以细分为三种遍历方式，区别在于访问根节点的时机：

遍历方式	访问顺序	特点
前序遍历	根→左→右	最先访问根，适合复制树结构
中序遍历	左→根→右	对于BST，输出有序序列
后序遍历	左→右→根	最后访问根，适合删除或计算子树信息

// 前序遍历（递归）
public void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

// 前序遍历（迭代）
public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // 先压右孩子，再压左孩子（栈是后进先出）
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

// 中序遍历（迭代）
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        // 先走到最左边
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // 弹出并访问
        curr = stack.pop();
        result.add(curr.val);
        // 转向右子树
        curr = curr.right;
    }
    return result;
}

// 后序遍历（迭代 - 反转法）
public List<Integer> postorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // 前序是根-左-右，这里变成根-右-左
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    // 反转得到左-右-根
    Collections.reverse(result);
    return result;
}

BFS：层层推进的波纹

BFS从起点开始，先访问所有距离为1的节点，然后访问所有距离为2的节点，以此类推。这种"波纹状"的扩展方式使BFS天然适合解决最短路径问题。

队列实现：先进先出的遍历

BFS的标准实现使用队列，代码结构非常清晰：

// BFS遍历图
public void bfs(int start, List<List<Integer>> graph) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    
    visited[start] = true;
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

层序遍历：BFS在二叉树上的经典应用

二叉树的层序遍历是BFS最经典的应用之一。通过在每一层开始时记录队列大小，可以区分不同层的节点：

// LeetCode 102. 二叉树层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

复杂度分析：谁更快？谁更省？

DFS和BFS的时间复杂度都是 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。这是因为每个顶点和每条边都只会被访问一次。对于树结构，边数 $E = V - 1$，所以复杂度简化为 $O(V)$。

空间复杂度则有所不同：

算法	空间复杂度	说明
DFS	$O(H)$	$H$ 为树的高度或图的深度，递归栈深度
BFS	$O(W)$	$W$ 为树的宽度或图的广度，队列最大长度

在最坏情况下：

DFS的空间复杂度为 $O(V)$（链状结构）
BFS的空间复杂度也为 $O(V)$（完全二叉树底层节点数为 $V/2$）

实际选择建议：对于深度大、宽度小的结构，BFS可能更省空间；对于宽度大、深度小的结构，DFS更省空间。在不确定的情况下，DFS通常内存占用更稳定。

何时选择DFS？何时选择BFS？

场景	推荐算法	原因
最短路径（无权图）	BFS	BFS按层遍历，最先到达目标的就是最短路径
连通分量统计	DFS/BFS	两者都可以，DFS代码更简洁
拓扑排序	DFS/BFS	DFS用后序遍历，BFS用入度表（Kahn算法）
环检测	DFS	DFS可以检测回边，判断是否有环
路径搜索（所有解）	DFS	DFS天然支持回溯，可以找到所有路径
层级相关问题	BFS	BFS天然按层遍历，方便处理层级信息

一个关键洞察：如果问题需要"最短"或"最少"的答案，BFS通常是更好的选择。如果需要"所有可能"或"存在性"的答案，DFS更合适。

LeetCode实战：DFS与BFS的经典题目

一、树结构遍历

LeetCode 104. 二叉树的最大深度

这是DFS最基础的应用。树的深度等于左子树深度和右子树深度的最大值加1。

// DFS递归解法
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// BFS解法
public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        depth++;
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}

LeetCode 226. 翻转二叉树

这是一道经典的DFS题目。交换每个节点的左右子树即可。

// DFS递归解法
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

LeetCode 236. 二叉树的最近公共祖先

这道题展示了DFS在后序遍历中的应用。当一个节点同时拥有p和q作为后代时，它就是最近公共祖先。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 基本情况：到达叶子节点或找到目标节点
    if (root == null || root == p || root == q) {
        return root;
    }
    
    // 在左右子树中搜索
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // 如果左右子树都找到了，当前节点就是LCA
    if (left != null && right != null) {
        return root;
    }
    
    // 返回非空的那一侧
    return left != null ? left : right;
}

二、图结构遍历

LeetCode 200. 岛屿数量

这是DFS/BFS在网格图上的经典应用。每找到一个'1’，就进行DFS/BFS将整个岛屿标记为已访问。

// DFS解法
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    
    int m = grid.length, 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') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    
    // 边界检查
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
        return;
    }
    
    // 标记为已访问
    grid[i][j] = '2';
    
    // 四个方向DFS
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j - 1);
    dfs(grid, i, j + 1);
}

// BFS解法
public int numIslandsBFS(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    
    int m = grid.length, n = grid[0].length;
    int count = 0;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                count++;
                Queue<int[]> queue = new LinkedList<>();
                queue.offer(new int[]{i, j});
                grid[i][j] = '2';
                
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] dir : dirs) {
                        int ni = cell[0] + dir[0];
                        int nj = cell[1] + dir[1];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == '1') {
                            grid[ni][nj] = '2';
                            queue.offer(new int[]{ni, nj});
                        }
                    }
                }
            }
        }
    }
    return count;
}

LeetCode 133. 克隆图

这道题需要在DFS/BFS过程中维护新旧节点的映射关系。

// DFS解法
public Node cloneGraph(Node node) {
    if (node == null) return null;
    
    Map<Node, Node> visited = new HashMap<>();
    return dfs(node, visited);
}

private Node dfs(Node node, Map<Node, Node> visited) {
    // 如果已经克隆过，直接返回
    if (visited.containsKey(node)) {
        return visited.get(node);
    }
    
    // 克隆当前节点
    Node clone = new Node(node.val);
    visited.put(node, clone);
    
    // 克隆所有邻居
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, visited));
    }
    
    return clone;
}

// BFS解法
public Node cloneGraphBFS(Node node) {
    if (node == null) return null;
    
    Map<Node, Node> visited = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    
    Node clone = new Node(node.val);
    visited.put(node, clone);
    queue.offer(node);
    
    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        
        for (Node neighbor : curr.neighbors) {
            if (!visited.containsKey(neighbor)) {
                visited.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            visited.get(curr).neighbors.add(visited.get(neighbor));
        }
    }
    
    return clone;
}

LeetCode 207. 课程表

这道题本质是检测有向图中是否存在环。可以使用DFS检测环，或使用BFS的拓扑排序（Kahn算法）。

// DFS检测环
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
    }
    
    // 0: 未访问, 1: 正在访问, 2: 已访问完成
    int[] state = new int[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        if (hasCycle(graph, i, state)) {
            return false;
        }
    }
    return true;
}

private boolean hasCycle(List<List<Integer>> graph, int node, int[] state) {
    if (state[node] == 1) return true;  // 发现环
    if (state[node] == 2) return false; // 已经访问过
    
    state[node] = 1;  // 标记为正在访问
    
    for (int neighbor : graph.get(node)) {
        if (hasCycle(graph, neighbor, state)) {
            return true;
        }
    }
    
    state[node] = 2;  // 标记为访问完成
    return false;
}

// BFS拓扑排序（Kahn算法）
public boolean canFinishBFS(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        
        for (int neighbor : graph.get(course)) {
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    return count == numCourses;
}

三、最短路径问题

LeetCode 127. 单词接龙

这道题要求最短转换序列的长度，是BFS求最短路径的典型应用。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord)) return 0;
    
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    int level = 1;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            
            if (word.equals(endWord)) {
                return level;
            }
            
            // 尝试改变每个位置的字符
            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    chars[j] = c;
                    String newWord = new String(chars);
                    
                    if (wordSet.contains(newWord)) {
                        queue.offer(newWord);
                        wordSet.remove(newWord);  // 避免重复访问
                    }
                }
                chars[j] = original;
            }
        }
        level++;
    }
    
    return 0;
}

LeetCode 130. 被围绕的区域

这道题的关键洞察是：任何与边界相连的’O’都不会被包围。我们可以从边界的’O’开始BFS/DFS标记所有不被包围的区域。

public void solve(char[][] board) {
    if (board == null || board.length == 0) return;
    
    int m = board.length, n = board[0].length;
    
    // 从边界的'O'开始标记
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O') dfs(board, 0, j);
        if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
    }
    
    // 遍历整个矩阵，还原标记，填充被包围的区域
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '#') board[i][j] = 'O';
        }
    }
}

private void dfs(char[][] board, int i, int j) {
    int m = board.length, n = board[0].length;
    
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
        return;
    }
    
    board[i][j] = '#';  // 标记为不被包围
    
    dfs(board, i - 1, j);
    dfs(board, i + 1, j);
    dfs(board, i, j - 1);
    dfs(board, i, j + 1);
}

题目模式总结

通过以上题目，可以总结出DFS和BFS在LeetCode上的几种常见模式：

DFS常见模式：

树的遍历（前/中/后序）
图的连通分量统计
路径搜索（所有路径）
环检测（三色标记法）
拓扑排序（后序遍历逆序）

BFS常见模式：

层序遍历
最短路径（无权图）
拓扑排序（Kahn算法）
从边界开始的填充问题

掌握这些模式，大多数DFS/BFS问题都能迎刃而解。记住：当问题涉及"最短"、“最少”、“层级"时，优先考虑BFS；当问题涉及"所有可能”、“存在性”、“路径搜索"时，优先考虑DFS。

参考资料

GeeksforGeeks. “Difference between BFS and DFS.” https://www.geeksforgeeks.org/dsa/difference-between-bfs-and-dfs/
VisuAlgo. “Graph Traversal (Depth/Breadth First Search).” https://visualgo.net/en/dfsbfs
LeetCode. “Depth-First Search Problem List.” https://leetcode.com/problem-list/depth-first-search/
LeetCode. “Breadth-First Search Problem List.” https://leetcode.com/problem-list/breadth-first-search/
Baeldung. “Depth First Search in Java.” https://www.baeldung.com/java-depth-first-search
LeetCode Discuss. “Iterative | Recursive | DFS & BFS Tree Traversal.” https://leetcode.com/discuss/post/937307/
Medium. “Leetcode Pattern 1 | BFS + DFS == 25% of the problems.” https://medium.com/leetcode-patterns/leetcode-pattern-1-bfs-dfs-25-of-the-problems-part-1-519450a84353

栈与队列：两种数据结构的哲学分野#

DFS：一条路走到黑#

递归实现：代码最简洁的形式#

迭代实现：显式栈的运用#

二叉树的三种DFS遍历#

BFS：层层推进的波纹#

队列实现：先进先出的遍历#

层序遍历：BFS在二叉树上的经典应用#

复杂度分析：谁更快？谁更省？#

何时选择DFS？何时选择BFS？#

LeetCode实战：DFS与BFS的经典题目#

一、树结构遍历#

LeetCode 104. 二叉树的最大深度#

LeetCode 226. 翻转二叉树#

LeetCode 236. 二叉树的最近公共祖先#

二、图结构遍历#

LeetCode 200. 岛屿数量#

LeetCode 133. 克隆图#

LeetCode 207. 课程表#

三、最短路径问题#

LeetCode 127. 单词接龙#

LeetCode 130. 被围绕的区域#

题目模式总结#

参考资料#

更多精彩内容

回溯算法:从决策树到剪枝优化的完整LeetCode通关指南

Tarjan算法为何能用一次DFS完成图论四大难题从强连通分量到桥与割点的完整LeetCode通关指南

二叉树遍历为何如此重要：从递归到Morris的四种实现方式与LeetCode完整通关指南

拓扑排序如何让任务有条不紊地执行：从Kahn算法到DFS的完整LeetCode通关指南

扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南