{ }codelper

学ぶ › JavaScript

アルゴリズム · 33

幅優先探索とトポロジカルソート

キューで近い所から広げて最少の歩数を求め、先にやることが前に来るように並べます。

幅優先探索（BFS）は出発点から近い所の順に広げていき、トポロジカルソートは「これを終えないとあれができない」という条件をすべて守る順番を作ります。
下の例は「a を終えないと b を始められない」という組を読み、1 番の仕事から矢印を最少で何回たどれば各仕事に着くか（着かなければ -1）と、条件を守って仕事をする順番を表示します。

const [[n, m], ...pairs] = require("fs").readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj = Array.from({ length: n + 1 }, () => []); // adj[a] = a를 끝내야 시작할 수 있는 일들const need = new Array(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 = new Array(n + 1).fill(-1); // -1이면 아직 안 간 곳dist[1] = 0;let queue = [1];let head = 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 = [];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 でなければもう見つけた所とみなすので、印と歩数を一度に書いています。
  • 格子でも同じです。
    マス一つが点で、上・下・左・右のマスが隣です。
    隣のリストを作る代わりに、2次元リストの単元の方向のリスト（di、dj）から隣のマスを求め、格子の外と壁を除きます。
  • トポロジカルソートは、BFS が終わったあと、空のキューで最初から別にもう一度回す処理です（出力の 2 行目）。
    同じ 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() でも先頭を取り出せますが、残りの値をすべて一つずつ前に詰めるので、スタックとキューの単元で見たように、値が多いと遅くなります
TypeScriptJavaScript と同じです。
型は 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 で埋めたベクターは 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 が最少の歩数を出すのは、どの矢印も同じ 1 歩のときです。
そしてトポロジカルソートでは、組「a b」が「a が先」という意味なら、adj[a] に b を入れて need[b] を増やします。
矢印が入ってくる側の数を数えるのです。

練習問題

  1. ストーブの暖かさが広がる教室8P0378
  2. 手がかりだけで決まる順位8P0381
  3. 扉が一つずつ閉まる博物館8P0291
  4. 先修科目を守る学期計画8P0197
  5. 古くなったファイルだけ作り直す8P0326
  6. 二つの水差しでぴったり量る手順8P0210
  7. 祭りの準備作業の余裕時間8P0303
  8. 島の地図8P0072