【唐叔学算法】第十天：广度优先遍历-探索图结构的逐层之旅

你是否曾为如何高效地解决图论中的搜索问题而苦恼？广度优先遍历算法，就像一位经验丰富的探险家，能帮你轻松探索图中的每个角落。今天，就让我们一起揭开广度优先遍历算法的神秘面纱，探索它在Java编程中的应用。

一、什么是广度优先遍历？

定义

广度优先遍历是一种用于遍历或搜索图（Graph）和树（Tree）数据结构的算法。它的核心思想是从某个起始节点开始，首先访问所有直接相连的一级邻居节点，然后再依次访问这些邻居的未访问过的邻居，以此类推，直到没有新的节点可以访问为止。

应用场景

广度优先遍历算法广泛应用于以下场景：

• 图论问题：判断两个节点是否相连、求解最短路径、拓扑排序等。
• 搜索问题：求解迷宫问题、八皇后问题等。
• 动态规划问题：求解背包问题、最长公共子序列等。
• 层次遍历：如二叉树的层序遍历。
• 游戏AI：实现简单的寻路算法等。

算法实现

广度优先遍历通常使用队列（Queue）作为辅助工具。具体步骤如下：

1. 将起始节点加入队列，并标记为已访问。
2. 当队列不为空时，重复以下操作：
   • 从队列头部取出一个节点进行处理。
   • 将该节点的所有未被访问过的相邻节点依次加入队列尾部，并标记它们为已访问。
3. 如果队列为空且仍有未访问的节点，则说明图是不连通的；否则，继续上述过程直到遍历完毕。

注意事项

• 防止重复访问：需要维护一个访问状态表来避免同一节点被多次处理。
• 边界条件：考虑空图、单节点等情况。
• 环图问题：注意处理图中的环，避免无线循环。
• 时间复杂度：对于稠密图，BFS的时间复杂度为O(V + E)，其中V表示顶点数，E表示边的数量。

二、实战解析

中等难度题目1 - 102. 二叉树的层序遍历

题目链接：102. 二叉树的层序遍历
题目描述：给定一个二叉树，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

解题思路

这个问题非常适合用广度优先遍历来解决。我们可以使用一个队列来保存当前层的所有节点，然后在每次迭代中处理完一层后再把下一层的所有子节点加入队列，这样就能保证按照层次顺序访问每个节点了。

Java代码实现

import java.util.*;

public class Solution {
    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 size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; ++i) {
                TreeNode curr = queue.poll();
                level.add(curr.val);
                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
            result.add(level);
        }

        return result;
    }
}

中等难度题目2 - 994. 腐烂的橘子

题目链接：994. 腐烂的橘子

题目描述：在给定的网格中，每个单元格可以包含新鲜橘子，烂掉的橘子或者空。烂掉的橘子会在几分钟内腐烂其四个方向上相邻的新鲜橘子。给你一个 fresh（新鲜的橘子数量）、一个 rot（烂掉的橘子数量）、一个 minutes（经过的时间总量），返回直到没有新鲜橘子为止的最短时间。

解题思路

使用队列来实现广度优先遍历，模拟橘子腐烂的过程。每次从队列中取出所有烂掉的橘子，然后尝试腐烂其四个方向上相邻的新鲜橘子。

Java代码实现

public int orangesRotting(int[][] grid) {
    int fresh = 0, rot = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
                rot++;
            } else if (grid[i][j] == 1) {
                fresh++;
            }
        }
    }
    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int[] direction : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                int x = cell[0] + direction[0], y = cell[1] + direction[1];
                if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
                    grid[x][y] = 2;
                    fresh--;
                    queue.offer(new int[]{x, y});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

三、更多LeetCode题目推荐

• 126. 单词接龙 II
• 127. 单词接龙
• 128. 最长连续序列
• 286. 墙与门
• 417. 太平洋大西洋水流问题
• 490. 迷宫
• 542. 01矩阵
• 630. 课程表 III
• 752. 打开转盘锁
• 815. 公交路线

四、总结

通过今天的分享，相信大家已经初步了解了广度优先遍历的基本原理及其在实际问题中的应用。作为一种强大的搜索工具，BFS能够帮助我们高效地解决许多涉及图和树结构的问题。希望各位读者朋友能够在实践中灵活运用这些知识，解决更多的编程挑战。

如果有任何疑问或建议，欢迎在评论区留言交流！我是唐叔，我们下次见！

希望这篇文章能够帮助大家更好地理解和应用广度优先遍历技术。如果喜欢这篇文章，别忘了点赞和分享哦！