跳到主要内容

DFS 与 BFS

问题​

DFS 和 BFS 在 Java 面试中的常见应用场景和题目？

答案​

DFS 模板​

DFS 递归模板（网格搜索）
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
        || visited[i][j] || grid[i][j] == 0) return;
    visited[i][j] = true;
    dfs(grid, i + 1, j, visited);
    dfs(grid, i - 1, j, visited);
    dfs(grid, i, j + 1, visited);
    dfs(grid, i, j - 1, visited);
}

BFS 模板​

BFS 层序遍历模板
int bfs(int[][] grid, int startX, int startY) {
    Queue<int[]> queue = new LinkedList<>();
    boolean[][] visited = new boolean[grid.length][grid[0].length];
    queue.offer(new int[]{startX, startY});
    visited[startX][startY] = true;
    int steps = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            // 到达目标：return steps
            for (int[] d : dirs) {
                int nx = cur[0] + d[0], ny = cur[1] + d[1];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length
                    && !visited[nx][ny] && grid[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;
}

岛屿的最大面积（LeetCode 695）​

DFS 计算连通区域面积
public int maxAreaOfIsland(int[][] grid) {
    int maxArea = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
    }
    return maxArea;
}

private int dfs(int[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
        || grid[i][j] != 1) return 0;
    grid[i][j] = 0;
    return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) 
             + dfs(grid, i, j+1) + dfs(grid, i, j-1);
}

腐烂的橘子（LeetCode 994）—— 多源 BFS​

所有腐烂橘子同时作为 BFS 起点
public int orangesRotting(int[][] grid) {
    Queue<int[]> queue = new LinkedList<>();
    int fresh = 0;
    
    // 所有腐烂橘子入队
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    }
    
    if (fresh == 0) return 0;
    int minutes = 0;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int nx = cur[0] + d[0], ny = cur[1] + d[1];
                if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length
                    && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    fresh--;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes - 1 : -1;
}

单词接龙（LeetCode 127）—— BFS 求最短转换路径​

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);
    Set<String> visited = new HashSet<>();
    visited.add(beginWord);
    int level = 1;
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String word = queue.poll();
            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char original = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[j] = c;
                    String newWord = new String(chars);
                    if (newWord.equals(endWord)) return level + 1;
                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        visited.add(newWord);
                        queue.offer(newWord);
                    }
                }
                chars[j] = original;
            }
        }
        level++;
    }
    return 0;
}

常见面试问题​

Q1: DFS 和 BFS 怎么选？​

答案：

场景选择原因
最短路径（无权）BFSBFS 按层扩展，第一次到达即最短
连通分量/路径存在DFS实现简单，递归即可
所有路径DFS + 回溯需要枚举所有可能
层级遍历BFS天然按层处理

Q2: DFS 可能栈溢出怎么办？​

答案：

  • 递归深度过大时改用迭代 DFS（显式栈）
  • 或用 BFS 替代
  • Java 默认栈大小约 512KB~1MB，可通过 -Xss 调整

Q3: 什么是多源 BFS？​

答案：

多个起点同时入队开始 BFS，适合"从多个源头同时扩散"的场景（如腐烂的橘子、01 矩阵最短距离）。

相关链接​