{ }codelper

学ぶ › Python

アルゴリズム · 32

グラフと深さ優先探索

誰と誰がつながっているかを書きとめ、行ける所をもれなくたどります。

グラフは、点（人、町、部屋）とそれらを結ぶ線（友だち関係、道、ドア）でできたデータです。
下の例は友だちの組を読んで人ごとの友だちリストを作り、1 番から友だちをたどって着いた順番と、たがいに行き来できる人どうしをまとめたグループの数を表示します。

n, m = map(int, input().split())adj = [[] for _ in range(n + 1)]  # adj[v] = v번의 친구들for _ in range(m):    a, b = map(int, input().split())    adj[a].append(b)  # 서로 친구라 양쪽에 넣어요    adj[b].append(a) seen = [False] * (n + 1)order = [] def dfs(v):  # 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요    seen[v] = True    order.append(v)    for w in adj[v]:        if not seen[w]:            dfs(w) dfs(1)print(*order) # 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = [False] * (n + 1)groups = 0for s in range(1, n + 1):    if seen[s]:        continue    groups += 1    seen[s] = True    stack = [s]    while stack:        v = stack.pop()        for w in adj[v]:            if not seen[w]:                seen[w] = True                stack.append(w)print(groups)
stdin
7 5
1 2
1 3
2 4
3 4
5 6
stdout
1 2 4 3
3

ポイント

  • 入力はふつう「a b」の組で来ます。
    これを人ごとに隣をまとめたリスト adj[v] に直しておきます（隣接リスト）。
    そうすれば「v の隣は誰か」が、組を見直さなくてもすぐ分かります。
    両方向につながる関係なら、adj[a] に b を、adj[b] に a を、両方とも入れます。
  • 番号が 1 から始まるなら、n + 1 個の場所を作って 0 番は空けておきます。
    番号をそのまま位置として使えます。
  • 深さ優先探索（DFS）は、今いる所に訪問済みの印（seen）を付け、まだ行っていない隣が出てきたらすぐそちらへ入ります。
    行き先がなくなったら来た所へ戻り、残りの隣を見ます。
    例の dfs(v) は番号 v だけを受け取り、adj・seen・order は関数の外に置いたものを共有します。
    例では 1 番の友だちは 2 番と 3 番ですが、2 番に入ったついでに 4 番まで行ってからやっと 3 番を見るので、順番は 1 2 4 3 です。
  • 印があるので、一人には一度しか入らず、友だち関係一つは両側から一度ずつしか見ません。
    だから仕事の量は、人数に組の数を足したぶんです。
  • 再帰の代わりにスタックを自分で使ってもかまいません。
    出発点を入れ、一つ取り出して、まだ行っていない隣に印を付けながら入れる、ということをスタックが空になるまで繰り返します。
    たどる順番は変わることがありますが（例をスタックで回すと 1 3 4 2）、着く人は同じです。
  • まだ印のない人から探索を新しく始めるたびに、グループが一つ増えます。
    例は {1, 2, 3, 4}、{5, 6}、{7} なので 3 です。

言語ごとの書き方

Pythonadj = [[] for _ in range(n + 1)]、adj[a].append(b)。
スタックはリストの append と pop() です
JavaScriptArray.from({ length: n + 1 }, () => [])、adj[a].push(b)。
スタックは配列の push と pop() です
TypeScriptJavaScript と同じです。
型は number[][]。
stack.pop() の型は number | undefined なので、空でないと確かめた場所では stack.pop()! と書きます
JavaArrayList<ArrayList<Integer>> に空の ArrayList を n + 1 個 add しておき、adj.get(a).add(b)。
スタックは ArrayDeque の push と pop です
C#new List<int>[n + 1] は場所がすべて null なので、一つずつ new List<int>() を入れます。
そのあと adj[a].Add(b)。
スタックは Stack<int> の Push と Pop です
C++std::vector<std::vector<int>> adj(n + 1) — 空のベクターが n + 1 個、別々にできます。
adj[a].push_back(b)。
スタックは vector の push_back、back()、pop_back() で作ります
C伸びるリストがありません。
int adj[MAX][MAX] と隣の数 deg[v] を置き、adj[a][deg[a]++] = b で入れます。
スタックも配列と番号 top で作ります
Craykon新リスト(n + 1, []) は場所ごとに別々の空リストを作ります。
adj[a].追加(b)、隣は それぞれ (w の中 adj[v])。
スタックにはリストの末尾を使います。
stack.追加(w) で入れ、stack[stack.個数 - 1] を読んでから stack.位置で取り除く(stack.個数 - 1) で取り除きます

よくある間違い

隣のリストを [[]] * n で作ったPython · JavaScript · TypeScript

adj = [[]] * 3
adj[1].append(2)
print(adj)

→ [[2], [2], [2]] — 空のリスト一つを三つの場所がいっしょに指しているので、1 番に入れた友だちが全員に入ります。JavaScript の new Array(3).fill([]) も同じです

場所ごとに新しく作ります：[[] for _ in range(n + 1)]、Array.from({ length: n + 1 }, () => [])。

訪問済みの印を付け忘れた

void dfs(int v) {
    order.push_back(v);
    for (int w : adj[v]) dfs(w);
}

→ 1 番と 2 番が友だちというだけで 1 → 2 → 1 → 2 … と果てしなく入り続け、スタックがあふれて SIGSEGV で落ちます。同じミスをすると、Python は RecursionError、JavaScript は RangeError、Java は StackOverflowError で止まり、C# は Stack overflow. と表示して落ち、Craykon は「関数の呼び出しが深すぎるので止めました」で止まります

入ったらすぐ seen[v] = true と印を付け、印のない隣にだけ入ります。

配列だけ作って、中にリストを入れなかったJava · C#

List<int>[] adj = new List<int>[3];
adj[1].Add(2);

→ NullReferenceException — 配列を作っただけでは、場所はすべて null です。Java で new ArrayList[3] と作っても、同じように NullPointerException で止まります

使う前に、ループで一つずつ adj[v] = new List<int>();（Java は new ArrayList<>()）を入れます。

言語ごとの違い
再帰の DFS は短く書けますが、人が一列に長くつながっていると、そのぶん深く入ります。
ジャッジでは、例の Python コードは 900 人が一列につながった入力は解けますが、1,100 人では RecursionError で止まります。
Craykon のコードは 1,100 人は解けますが、5,000 人で止まります。
n が数千を超えうるなら、最初からスタックで書きましょう。

練習問題

  1. 分かれ道のメモをたどる8P0380
  2. かくれんぼの鬼が歩いた道8P0377
  3. 友だちの輪8P0118
  4. 折りたたまれた返信ツリーの行番号8P0292
  5. 共通の友だちがいちばん多い人8P0293
  6. 古くなったファイルだけ作り直す8P0326
  7. 鍵を拾いながら手さぐりで進む洞窟探検8P0190
  8. 祭りの準備作業の余裕時間8P0303