算法刷题系列（十）：队列——先进先出与广度优先搜索

算法刷题系列（十）：队列——先进先出与广度优先搜索

上一篇的栈按“最近加入的状态优先”处理；队列则按“最早加入的状态优先”。这个先进先出（FIFO）顺序适合模拟排队，也正是广度优先搜索（BFS）按层扩展状态的基础。

本篇先介绍队列操作，再用一个原创的无权路线图例子寻找最少边数路径，并分别用 Java 和 Python 实现。后续树的层序遍历、图论 BFS 和滑动窗口都会再次用到队列或队列变体。

一、队列是什么？

队列从队尾加入元素，从队头移除元素：

• enqueue(x)：加入队尾；
• dequeue()：移除并返回队头；
• peek()：查看队头；
• isEmpty()：判断是否为空。

队列遵循 FIFO（First In, First Out，先进先出）。先进入队列的元素先离开。

常见实现使用循环数组、链表或语言提供的双端队列。普通队列的加入和移除通常为 O(1)；如果用固定数组实现，需要通过首尾下标循环利用空间，避免每次出队都移动剩余元素。

二、为什么 BFS 使用队列？

在无权图中，每条边的代价都相同。若从起点开始：

• 距离起点 0 条边的节点先处理；
• 再处理距离 1 条边的节点；
• 然后处理距离 2 条边的节点；
• 依此类推。

队列的 FIFO 顺序保证先发现的浅层节点先扩展。因此第一次到达一个节点时，得到的就是从起点到它的最少边数路径。

这个保证依赖于无权图或所有边代价相同。如果边权不同，普通 BFS 不一定能找到最短加权路径，需使用适合边权条件的算法，例如后续会讲到的 Dijkstra。

三、原创例子：寻找最少换乘段数

把地点看成顶点，把可直接到达的路线看成无向边：

A ─ B ─ D
│   │
C ─ E ─ F

用邻接表表示为：

A: B, C
B: A, D, E
C: A, E
D: B, F
E: B, C, F
F: D, E

从 A 到 F，可能路径包括：

• A → B → D → F：3 条边；
• A → C → E → F：3 条边；
• A → B → E → F：3 条边。

BFS 按层访问：

层数	节点
0	A
1	B, C
2	D, E
3	F

第一次发现 F 时，距离是 3 条边，已经是最少边数。

为了还原路径，除了记录 distance[next]，还记录 parent[next]：每个节点首次被发现时，保存从哪个节点到达它。搜索结束后从终点沿 parent 反向回溯，再反转路径。

四、BFS 的关键不变量

实现时维护以下规则：

1. 队列中保存“已经发现、但邻居尚未全部检查”的节点。
2. 节点第一次入队时就标记为已访问，避免其他边重复入队。
3. 新节点的距离等于当前节点距离加 1。
4. 若需要还原路径，只在第一次发现节点时设置 parent。

访问标记要在入队时设置，而不是等出队时设置。否则同一节点可能被多个相邻节点重复加入队列，导致重复工作，甚至破坏 parent 的一致性。

五、Java 实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class BreadthFirstSearch {
    public static List<String> shortestPath(
            Map<String, List<String>> graph,
            String start,
            String target) {
        if (graph == null || start == null || target == null) {
            throw new IllegalArgumentException("Graph and nodes must not be null");
        }
        if (!graph.containsKey(start)) {
            return Collections.emptyList();
        }

        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        Map<String, String> parent = new HashMap<>();

        visited.add(start);
        queue.addLast(start);

        while (!queue.isEmpty()) {
            String current = queue.removeFirst();
            if (current.equals(target)) {
                break;
            }

            for (String next : graph.getOrDefault(current, Collections.emptyList())) {
                if (visited.add(next)) {
                    parent.put(next, current);
                    queue.addLast(next);
                }
            }
        }

        if (!visited.contains(target)) {
            return Collections.emptyList();
        }

        List<String> path = new ArrayList<>();
        for (String node = target; node != null; node = parent.get(node)) {
            path.add(node);
            if (node.equals(start)) {
                break;
            }
        }
        Collections.reverse(path);
        return path;
    }
}

图中邻居的遍历顺序可能影响找到哪一条最短路径，但不影响最短边数。若题目要求字典序最小等额外条件，需要额外规定邻居排序或改变搜索策略。

六、Python 实现

from collections import deque

def shortest_path(
    graph: dict[str, list[str]], start: str, target: str
) -> list[str]:
    if graph is None or start is None or target is None:
        raise ValueError("graph and nodes must not be None")
    if start not in graph:
        return []

    queue = deque([start])
    visited = {start}
    parent: dict[str, str | None] = {start: None}

    while queue:
        current = queue.popleft()
        if current == target:
            break

        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current
                queue.append(neighbor)

    if target not in visited:
        return []

    path = []
    node: str | None = target
    while node is not None:
        path.append(node)
        node = parent[node]
    path.reverse()
    return path

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "E"],
    "D": ["B", "F"],
    "E": ["B", "C", "F"],
    "F": ["D", "E"],
}

path = shortest_path(graph, "A", "F")
assert len(path) - 1 == 3
assert path[0] == "A" and path[-1] == "F"
assert shortest_path(graph, "A", "A") == ["A"]
assert shortest_path({"A": [], "B": []}, "A", "B") == []
assert shortest_path({"A": ["Z"]}, "A", "Z") == ["A", "Z"]

这个例子可能返回 A → B → D → F 或 A → B → E → F 等最短路径，具体路径由邻接表中邻居的顺序决定。测试只检查路径有效性和最短距离，不依赖某一条并列最优路径。

七、复杂度分析

使用邻接表时，BFS 会把每个顶点最多加入队列一次，并检查每条边：

• 时间复杂度： O(V + E)；
• 额外空间复杂度： O(V)。

其中 V 是顶点数，E 是边数。还原路径需要保存 parent，属于 O(V) 空间。

若图用邻接矩阵表示，检查一个顶点的邻居需要扫描整行，整体时间通常为 O(V²)。图较稀疏时，邻接表更节省空间和遍历时间。

八、队列的其他应用

• 树的层序遍历：逐层访问节点。
• 多源扩散：把多个起点同时加入队列，计算到最近起点的距离。
• 任务调度：先到达的任务先处理。
• 生产者/消费者缓冲区：按顺序传递待处理工作。
• 滑动窗口：用双端队列维护窗口内仍有效的候选索引。

需要从两端插入或删除时，使用双端队列；不要用普通队列接口模拟所有操作。

九、常见错误

1. 用数组头部删除来模拟队列：删除后移动元素可能造成 O(n) 操作，应使用真正的队列或双端队列。
2. 出队时才标记访问：同一个顶点可能被重复入队，应在首次入队时标记。
3. 对有权图直接使用普通 BFS：边权不相同时，先发现不代表总代价最小。
4. 只保存距离却需要输出路线：需要额外保存 parent 或前驱。
5. 图不连通时没有处理不可达：搜索结束后应判断目标是否被访问。
6. 测试依赖并列路径顺序：多条最短路径都合法，除非题目对路径有额外排序要求。

十、与后续主题的连接

栈和队列分别体现 LIFO 与 FIFO。队列中的先进先出顺序使 BFS 能按距离层次扩展，是图论和树遍历的基础；之后学习链表时，还会比较它与数组、队列在插入和访问上的差异。

下一篇将转向链表，讨论节点之间通过引用连接时，如何安全地插入、删除和重连节点。

小结

队列按进入顺序处理元素，适合任务排队和逐层遍历。BFS 在无权图中利用 FIFO 顺序，使较短路径层先于较长路径层处理；首次发现节点即可确定最少边数距离。实现时要在入队时标记访问，必要时记录 parent 还原路径。