广度优先遍历

广度优先搜索（BFS）是一种遍历或搜索数据结构（如树或图）的算法。该算法从根节点开始，沿着每个可能的分支向下搜索，直到找到目标或访问了所有节点。BFS 通常使用队列来实现。

BFS 算法可以用于查找最短路径，因为它在访问的节点数量相同时总是先访问距离起始节点更近的节点。

下面是 BFS 算法的伪代码：

BFS(G, s):
    create a queue Q
    enqueue s onto Q
    mark s
    while Q is not empty:
        dequeue an item from Q into v
        for each neighbor w of v in G:
            if w is not marked:
                mark w
                enqueue w onto Q

其中 G 是图，s 是起始节点。

下面是一个简单的 Java 实现，假设图是用邻接表表示的：

public static void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()]; // 标记是否已访问过
    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);
            }
        }
    }
}

在上面的实现中，我们使用一个 boolean 类型的数组来标记每个节点是否已经被访问过，使用一个队列来保存需要访问的节点。我们从起始节点开始遍历，首先将其标记为已访问，并将其加入队列。然后，我们从队列中取出节点，并遍历其邻居节点。对于每个邻居节点，如果它还没有被访问过，则将其标记为已访问，并将其加入队列。这样，我们就可以一层一层地遍历整个图，直到遍历完所有节点。