アルゴリズム · 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)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[v] = v번의 친구들for (const [a, b] of pairs.slice(0, m)) { adj[a].push(b); // 서로 친구라 양쪽에 넣어요 adj[b].push(a);} let seen = new Array(n + 1).fill(false);const order = []; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요function dfs(v) { seen[v] = true; order.push(v); for (const w of adj[v]) { if (!seen[w]) dfs(w); }} dfs(1);console.log(order.join(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = new Array(n + 1).fill(false);let groups = 0;for (let s = 1; s <= n; s++) { if (seen[s]) continue; groups++; seen[s] = true; const stack = [s]; while (stack.length > 0) { const v = stack.pop(); for (const w of adj[v]) { if (!seen[w]) { seen[w] = true; stack.push(w); } } }}console.log(groups);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[v] = v번의 친구들for (const [a, b] of pairs.slice(0, m)) { adj[a].push(b); // 서로 친구라 양쪽에 넣어요 adj[b].push(a);} let seen: boolean[] = new Array<boolean>(n + 1).fill(false);const order: number[] = []; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요function dfs(v: number): void { seen[v] = true; order.push(v); for (const w of adj[v]) { if (!seen[w]) dfs(w); }} dfs(1);console.log(order.join(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = new Array<boolean>(n + 1).fill(false);let groups: number = 0;for (let s = 1; s <= n; s++) { if (seen[s]) continue; groups++; seen[s] = true; const stack: number[] = [s]; while (stack.length > 0) { const v = stack.pop()!; for (const w of adj[v]) { if (!seen[w]) { seen[w] = true; stack.push(w); } } }}console.log(groups);import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Scanner; public class Main { static ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adj.get(v) = v번의 친구들 static boolean[] seen; static StringBuilder order = new StringBuilder(); // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요 static void dfs(int v) { seen[v] = true; order.append(order.length() > 0 ? " " : "").append(v); for (int w : adj.get(v)) { if (!seen[w]) dfs(w); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); for (int v = 0; v <= n; v++) adj.add(new ArrayList<>()); // 빈 목록을 사람마다 하나씩 새로 for (int i = 0; i < m; i++) { int a = sc.nextInt(), b = sc.nextInt(); adj.get(a).add(b); // 서로 친구라 양쪽에 넣어요 adj.get(b).add(a); } seen = new boolean[n + 1]; dfs(1); System.out.println(order); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나 seen = new boolean[n + 1]; int groups = 0; for (int s = 1; s <= n; s++) { if (seen[s]) continue; groups++; seen[s] = true; ArrayDeque<Integer> stack = new ArrayDeque<>(); stack.push(s); while (!stack.isEmpty()) { int v = stack.pop(); for (int w : adj.get(v)) { if (!seen[w]) { seen[w] = true; stack.push(w); } } } } System.out.println(groups); }}using System;using System.Collections.Generic;using System.Linq; class Program{ static List<int>[] adj; // adj[v] = v번의 친구들 static bool[] seen; static List<int> order = new List<int>(); // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요 static void Dfs(int v) { seen[v] = true; order.Add(v); foreach (int w in adj[v]) { if (!seen[w]) Dfs(w); } } static void Main() { int[] nm = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int n = nm[0], m = nm[1]; adj = new List<int>[n + 1]; for (int v = 0; v <= n; v++) adj[v] = new List<int>(); // 칸마다 빈 목록을 하나씩 새로 for (int i = 0; i < m; i++) { int[] ab = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int a = ab[0], b = ab[1]; adj[a].Add(b); // 서로 친구라 양쪽에 넣어요 adj[b].Add(a); } seen = new bool[n + 1]; Dfs(1); Console.WriteLine(string.Join(" ", order)); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나 seen = new bool[n + 1]; int groups = 0; for (int s = 1; s <= n; s++) { if (seen[s]) continue; groups++; seen[s] = true; var stack = new Stack<int>(); stack.Push(s); while (stack.Count > 0) { int v = stack.Pop(); foreach (int w in adj[v]) { if (!seen[w]) { seen[w] = true; stack.Push(w); } } } } Console.WriteLine(groups); }}#include <iostream>#include <vector> std::vector<std::vector<int>> adj; // adj[v] = v번의 친구들std::vector<bool> seen;std::vector<int> order; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요void dfs(int v) { seen[v] = true; order.push_back(v); for (int w : adj[v]) { if (!seen[w]) dfs(w); }} int main() { int n, m; std::cin >> n >> m; adj.resize(n + 1); for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; adj[a].push_back(b); // 서로 친구라 양쪽에 넣어요 adj[b].push_back(a); } seen.assign(n + 1, false); dfs(1); for (size_t i = 0; i < order.size(); i++) std::cout << (i > 0 ? " " : "") << order[i]; std::cout << '\n'; // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나 seen.assign(n + 1, false); int groups = 0; for (int s = 1; s <= n; s++) { if (seen[s]) continue; groups++; seen[s] = true; std::vector<int> stack = {s}; while (!stack.empty()) { int v = stack.back(); stack.pop_back(); for (int w : adj[v]) { if (!seen[w]) { seen[w] = true; stack.push_back(w); } } } } std::cout << groups << '\n';}#include <stdio.h>#include <string.h> #define MAX 101 // 사람은 100명까지라고 정해 둬요 int adj[MAX][MAX], deg[MAX]; // adj[v][0..deg[v]-1] = v번의 친구들int seen[MAX], order[MAX], count = 0; // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요void dfs(int v) { seen[v] = 1; order[count++] = v; for (int i = 0; i < deg[v]; i++) { int w = adj[v][i]; if (!seen[w]) dfs(w); }} int main(void) { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); adj[a][deg[a]++] = b; // 서로 친구라 양쪽에 넣어요 adj[b][deg[b]++] = a; } dfs(1); for (int i = 0; i < count; i++) printf(i > 0 ? " %d" : "%d", order[i]); printf("\n"); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나 memset(seen, 0, sizeof seen); int groups = 0, stack[MAX]; for (int s = 1; s <= n; s++) { if (seen[s]) continue; groups++; seen[s] = 1; int top = 0; stack[top++] = s; while (top > 0) { int v = stack[--top]; for (int i = 0; i < deg[v]; i++) { int w = adj[v][i]; if (!seen[w]) { seen[w] = 1; stack[top++] = w; } } } } printf("%d\n", groups); return 0;}// 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요dfs(v){ seen[v] = 真; order.追加(v); それぞれ (w の中 adj[v]) { もし (!seen[w]) { dfs(w); } }} nm = コンソール.数読み();n = nm[0];m = nm[1];adj = 新リスト(n + 1, []); // adj[v] = v번의 친구들繰り返す (i = 0; i < m; i++){ ab = コンソール.数読み(); a = ab[0]; b = ab[1]; adj[a].追加(b); // 서로 친구라 양쪽에 넣어요 adj[b].追加(a);} seen = 新リスト(n + 1, 偽);order = [];dfs(1);コンソール.書く(order.つなぐ(" ")); // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나seen = 新リスト(n + 1, 偽);groups = 0;繰り返す (s = 1; s <= n; s++){ もし (seen[s]) { 次へ; } groups++; seen[s] = 真; stack = [s]; 間 (stack.個数 > 0) { v = stack[stack.個数 - 1]; stack.位置で取り除く(stack.個数 - 1); それぞれ (w の中 adj[v]) { もし (!seen[w]) { seen[w] = 真; stack.追加(w); } } }}コンソール.書く(groups);7 5 1 2 1 3 2 4 3 4 5 6
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 です。
言語ごとの書き方
| Python | adj = [[] for _ in range(n + 1)]、adj[a].append(b)。スタックはリストの append と pop() です |
|---|---|
| JavaScript | Array.from({ length: n + 1 }, () => [])、adj[a].push(b)。スタックは配列の push と pop() です |
| TypeScript | JavaScript と同じです。 型は number[][]。stack.pop() の型は number | undefined なので、空でないと確かめた場所では stack.pop()! と書きます |
| Java | ArrayList<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) で取り除きます |
よくある間違い
訪問済みの印を付け忘れた
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 と印を付け、印のない隣にだけ入ります。
隣のリストを [[]] * 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 }, () => [])。
配列だけ作って、中にリストを入れなかった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 人では
Craykon のコードは 1,100 人は解けますが、5,000 人で止まります。
n が数千を超えうるなら、最初からスタックで書きましょう。
再帰の DFS は短く書けますが、人が一列に長くつながっていると、そのぶん深く入ります。
ジャッジでは、例の Python コードは 900 人が一列につながった入力は解けますが、1,100 人では
RecursionError で止まります。Craykon のコードは 1,100 人は解けますが、5,000 人で止まります。
n が数千を超えうるなら、最初からスタックで書きましょう。