{ }codelper

学习 › TypeScript

算法 · 33

广度优先搜索与拓扑排序

用队列从近处向外扩展求最少步数，并把任务排成先决条件在前的顺序。

广度优先搜索（BFS）从起点出发，由近到远一层层扩展；拓扑排序则排出一个顺序，让所有“先做完这个才能做那个”的条件都得到满足。
下面的例子读入表示“做完 a 才能开始 b”的一对对数字，输出从 1 号任务最少沿箭头走几次能到各个任务（到不了输出 -1），以及一个满足条件的做任务顺序。

import { readFileSync } from "node:fs";const [[n, m], ...pairs]: number[][] = readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj: number[][] = Array.from({ length: n + 1 }, () => []); // adj[a] = a를 끝내야 시작할 수 있는 일들const need: number[] = new Array<number>(n + 1).fill(0); // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수for (const [a, b] of pairs.slice(0, m)) {  adj[a].push(b);  need[b]++;} // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지const dist: number[] = new Array<number>(n + 1).fill(-1); // -1이면 아직 안 간 곳dist[1] = 0;let queue: number[] = [1];let head: number = 0; // 큐의 맨 앞 자리. 꺼낼 때마다 한 칸씩 뒤로 가요while (head < queue.length) {  const v = queue[head++];  for (const w of adj[v]) {    if (dist[w] === -1) {      dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요      queue.push(w);    }  }}console.log(dist.slice(1).join(" ")); // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요const order: number[] = [];queue = [];head = 0;for (let v = 1; v <= n; v++) {  if (need[v] === 0) queue.push(v);}while (head < queue.length) {  const v = queue[head++];  order.push(v);  for (const w of adj[v]) {    need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요    if (need[w] === 0) queue.push(w);  }}console.log(order.join(" "));
stdin
6 6
1 2
2 3
3 4
1 4
4 5
6 3
stdout
0 1 2 1 2 -1
1 6 2 3 4 5

要点

  • BFS 把“已经找到、但还没看过邻居的地方”放在队列里。
    先把起点以 0 步放进去，然后重复到队列为空：取出队首，对每个还没到过的邻居写下 dist[w] = dist[v] + 1，并把它放到队尾。
  • 队列先进先出，所以出来的顺序是 0 步的地方、1 步的地方、2 步的地方。
    因此一个地方第一次被找到时的步数就是最少步数。
    例子里 4 号也能经 1 → 2 → 3 → 4 到达，但先由 1 → 4 找到，所以是 1。
  • 标记要在放入队列时做。
    例子把 dist 不是 -1 的地方当作已经找到，所以标记和步数是一次写下的。
  • 在网格上也一样。
    一个格子就是一个点，上、下、左、右的格子是邻居。
    不用建邻居列表，而是用二维列表那一课的方向列表（di、dj）求出相邻的格子，再去掉网格外面的和墙。
  • 拓扑排序是 BFS 结束之后，用一个空队列从头另做的一遍（输出的第二行）。
    它用同一个 adj，但不用 dist。
    它为每个任务数一个 need：还没做完的先决任务有几个。
    把 need 为 0 的任务放进队列；取出一个，写进顺序里，再把等着它的那些任务的 need 各减 1。
    减到 0 的任务现在可以做了，就放进队列。
  • 满足条件的顺序可能不止一个（例子里 1 6 2 3 4 5 和 6 1 2 3 4 5 都对）。
    如果条件成了环（2 → 3 → 2），环里的任务 need 始终到不了 0，就不会出现在顺序里。
    所以顺序的长度比 n 短，就说明有环。

各语言的写法

Pythonfrom collections import deque — 用 queue.append(w) 放入，用 queue.popleft() 取出队首。
初始值像 deque([1]) 这样给
JavaScript没有专门的队列。
用 push 放进数组，另设队首位置 head，用 queue[head++] 取出。
queue.shift() 也能取出队首，但剩下的值都要往前挪一位，就像栈与队列那一课看到的，值一多就慢
TypeScript和 JavaScript 一样。
类型是 number[]
JavaArrayDeque<Integer> — 用 queue.add(w) 放入，用 queue.poll() 取出队首。
新建的 int[] 全是 0，所以用 Arrays.fill(dist, -1) 改掉
C#Queue<int> — 用 Enqueue(w) 放入，用 Dequeue() 取出队首。
填满 -1 的数组是 Enumerable.Repeat(-1, n + 1).ToArray()
C++std::queue<int> — 用 push(w) 放入。
用 front() 读队首，用 pop() 去掉（pop() 不返回值）。
填满 -1 的 vector 是 std::vector<int> dist(n + 1, -1)
C没有队列，所以用一个数组和两个下标来做。
用 queue[tail++] = w 放入，用 queue[head++] 取出。
head < tail 就表示还有剩下的
Craykon用 queue.添加(w) 放到列表末尾，另设队首位置 head，读 queue[head] 之后 head++。
当 (head < queue.数量) 就表示还有剩下的。
填满 -1 的列表是 新列表(n + 1, -1)

常见错误

从队列取出时才做标记

int v = queue.front();
queue.pop();
seen[v] = true; // 取出时才标记
for (int w : adj[v]) {
    if (!seen[w]) {
        dist[w] = dist[v] + 1;
        queue.push(w);
    }
}

→ 对 1 → 2、1 → 3、2 → 3 会输出 0 1 2（正确答案是 0 1 1）。3 号还在队列里等着的时候，2 号又把 3 号放进去一次，并把步数改写成 2

就在放入队列的那个地方做标记。
这样每个地方只会进队列一次。

不是从队首而是从队尾取出Python · JavaScript · TypeScript

adj = [[], [2, 3], [5], [4], [5], []]
dist = [-1] * 6
dist[1] = 0
queue = [1]
while queue:
    v = queue.pop()
    for w in adj[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            queue.append(w)
print(*dist[1:])

→ 0 1 1 2 3 — 正确答案是 0 1 1 2 2。pop() 取出的是最后放入的那个，于是它不是队列而是栈，会先往远处钻。JavaScript 数组的 pop() 也一样

用 deque 的 popleft() 取出队首。
JavaScript 另设下标 head，用 queue[head++] 取出。

没有检查顺序的长度

// 1 → 2, 2 → 3, 3 → 2
while (!queue.isEmpty()) {
    int v = queue.poll();
    order.add(v);
    for (int w : adj.get(v)) {
        need[w]--;
        if (need[w] == 0) queue.add(w);
    }
}
System.out.println(order);

→ [1] — 没有报错就结束了，但少了 2 号和 3 号。它们互相等待，need 到不了 0

结束后检查顺序里是否有 n 个任务：if (order.size() < n)。
不够就说明有环，不可能全部做完。

各语言的差异
只有每个箭头都算同样的一步时，BFS 得到的才是最少步数。
另外在拓扑排序里，如果一对“a b”表示“a 在先”，就把 b 放进 adj[a]，并把 need[b] 加 1：数的是指向这个任务的箭头有几个。

练习题

  1. 炉子的暖意在教室里扩散8P0378
  2. 只凭线索就能确定的名次8P0381
  3. 门一扇扇上锁的博物馆8P0291
  4. 遵守先修课的学期计划8P0197
  5. 只重做过期的文件8P0326
  6. 用两个水壶刚好量出的操作顺序8P0210
  7. 庆典准备工作的宽裕时间8P0303
  8. 岛屿地图8P0072