算法 BFS DFS

BFS DFS 解题模板

利用二叉树解释BFS和DFS的基本算法

Posted by Jeremy Song on 2022-04-06
Estimated Reading Time 3 Minutes
Words 693 In Total
Viewed Times

今天在网上看到了两篇关于DFS和BFS的讲解，文章很不错。刚好最近也在学习BFS和DFS的算法。这里就把两篇文章中的解题模板摘抄出来了。

因为我个人的需要，这里仅仅展示解题模板，不做过多的讲解。文章是人家的，我就不做过多的搬运了。有兴趣的朋友可以在文章末尾点击链接查看原文。

二叉树DFS遍历

1
2
3
4
5
6
7
void dfs(TreeNode root){
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

二叉树BFS遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

二叉树BFS层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i < n; i++) { 
            // 变量 i 无实际意义，只是为了循环 n 次
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Queue<TreeNode> nextQueue = new ArrayDeque<>();
        while(!queue.isEmpty()) { 
            // 变量 i 无实际意义，只是为了循环 n 次
            TreeNode node = queue.poll();
            if (node.left != null) {
                nextQueue.add(node.left);
            }
            if (node.right != null) {
                nextQueue.add(node.right);
            }
        }
        queue.addAll(nextQueue);
    }
}

网格 DFS 遍历的框架代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    // 如果坐标 (r, c) 超出了网格范围，直接返回
    if (!inArea(grid, r, c)) {
        return;
    }
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
         && 0 <= c && c < grid[0].length;
}

加入避免重复遍历的语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果这个格子不是岛屿，直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 将格子标记为「已遍历过」
    
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
         && 0 <= c && c < grid[0].length;
}

参考资料

欢迎关注我的公众号 须弥零一，跟我一起学习IT知识。

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！

特色标签
算法 BFS DFS
链友
ESC