{ }codelper

Learn › TypeScript

Algorithms · 33

Breadth-first search and topological sort

Spread out from the nearest places with a queue to get the fewest steps, and line tasks up so prerequisites come first.

Breadth-first search (BFS) spreads out from the start, nearest places first, and a topological sort makes an order that keeps every rule of the form "this must be finished before that".
The example below reads pairs meaning "a must be finished before b can start", then prints the fewest arrows you must follow from task 1 to reach each task (-1 if it cannot be reached), and an order for doing the tasks that keeps every rule.

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

Key points

  • BFS keeps in a queue the places it has found but whose neighbours it has not looked at yet.
    Put the start in with 0 steps, then repeat until the queue is empty: take the front one out, and for each neighbour not reached yet, write dist[w] = dist[v] + 1 and add it to the back.
  • A queue gives back first what went in first, so places come out in order of 0 steps, 1 step, 2 steps.
    That is why the step count when a place is first found is the fewest possible.
    In the example, task 4 can be reached by 1 → 2 → 3 → 4, but it is found first by 1 → 4, so its answer is 1.
  • Mark a place when you add it to the queue.
    The example treats any dist other than -1 as already found, so the mark and the step count are written at once.
  • It works the same on a grid.
    Each cell is a point and the cells above, below, left and right are its neighbours.
    Instead of building neighbour lists, get the neighbouring cells from the direction lists of the 2D lists lesson (di, dj), and skip the ones outside the grid or inside a wall.
  • The topological sort is a second, separate pass that starts over with an empty queue after the BFS has finished (it gives the second output line).
    It uses the same adj but not dist.
    It counts, for each task, need: how many of its prerequisites are not finished yet.
    Put the tasks whose need is 0 in a queue; take one out, write it in the order, and lower by 1 the need of every task that was waiting for it.
    A task that drops to 0 can now be done, so it goes into the queue.
  • There can be several orders that keep the rules (in the example both 1 6 2 3 4 5 and 6 1 2 3 4 5 are right).
    If the rules form a cycle (2 → 3 → 2), the need of the tasks in the cycle never reaches 0 and they are left out.
    So an order shorter than n means there is a cycle.

How each language writes it

Pythonfrom collections import deque — add with queue.append(w) and take the front with queue.popleft().
Give it its first value like deque([1])
JavaScriptThere is no separate queue.
Add to an array with push, keep the front position in head, and take out with queue[head++].
queue.shift() also takes the front one out, but it moves every remaining value up one place, so it is slow with many values, as the stacks and queues lesson showed
TypeScriptSame as JavaScript.
The type is number[]
JavaArrayDeque<Integer> — add with queue.add(w) and take the front with queue.poll().
A new int[] is filled with 0, so change it with Arrays.fill(dist, -1)
C#Queue<int> — add with Enqueue(w) and take the front with Dequeue().
An array filled with -1 is Enumerable.Repeat(-1, n + 1).ToArray()
C++std::queue<int> — add with push(w).
Read the front with front() and remove it with pop() (pop() returns nothing).
A vector filled with -1 is std::vector<int> dist(n + 1, -1)
CThere is no queue, so build one from an array and two indexes.
Add with queue[tail++] = w and take out with queue[head++].
While head < tail, something is still waiting
CraykonAdd to the end of a list with queue.Add(w), keep the front position in head, read queue[head] and then head++.
while (head < queue.Count) means something is still waiting.
A list filled with -1 is NewList(n + 1, -1)

Common mistakes

Marking when taking out of the queue

int v = queue.front();
queue.pop();
seen[v] = true; // mark when taking out
for (int w : adj[v]) {
    if (!seen[w]) {
        dist[w] = dist[v] + 1;
        queue.push(w);
    }
}

→ With 1 → 2, 1 → 3 and 2 → 3 it prints 0 1 2 (the right answer is 0 1 1). While task 3 waits in the queue, task 2 adds it again and overwrites its step count with 2

Mark at the very place where you add to the queue.
Then each place enters the queue only once.

Taking from the back instead of the frontPython · 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 — the right answer is 0 1 1 2 2. pop() takes out the item added last, so this is a stack, not a queue, and it digs into far places first. pop() on a JavaScript array does the same

Take the front with popleft() on a deque.
In JavaScript keep a head index and take out with queue[head++].

Not checking the length of the order

// 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] — it ends without an error, but tasks 2 and 3 are missing. They wait for each other, so their need never reaches 0

After the loop, check that the order holds n tasks: if (order.size() < n).
If it holds fewer, there is a cycle and not everything can be done.

How languages differ
BFS gives the fewest steps only when every arrow counts as exactly one step.
And in a topological sort, if a pair "a b" means "a first", put b in adj[a] and raise need[b]: you count the arrows coming into a task.

Practice

  1. Stove warmth spreading through a classroom8P0378
  2. Ranks fixed by the clues alone8P0381
  3. The museum whose doors lock one by one8P0291
  4. A semester plan that keeps prerequisites8P0197
  5. Rebuild only the stale files8P0326
  6. The order of moves to measure with two jugs8P0210
  7. Slack time of festival tasks8P0303
  8. Island map8P0072