edubun
日本語
English한국어EspañolPortuguêsFrançaisDeutschItalianoРусский日本語
ホーム›プログラミング›アルゴリズム

グラフの探索：BFSとDFS

1736年、レオンハルト・オイラーは、ケーニヒスベルクの7つの橋をどれもちょうど1回ずつ渡る散歩はないことを示しました。グラフ理論はこの答えから始まりました。

点と線

グラフとは、頂点またはノードと呼ばれる点の集まりを、辺と呼ばれる線で結んだものです。考え方は素朴ですが、とても幅広いものにあてはまります。道路で結ばれた都市、リンクで結ばれたウェブページ、友人関係で結ばれた人々、壁のないところでつながった迷路のマスなどです。問題をいったんグラフとしてかけば、ひと握りの同じアルゴリズムで「ここからあそこへ行けるか？」や「いちばん短い道は？」といった問いに答えられます。

背景ケーニヒスベルク（今のカリーニングラード）の町には、川の2つの島と両岸を結ぶ7つの橋がありました。人々は、どの橋もちょうど1回ずつ渡る散歩ができるかと考えました。1736年、レオンハルト・オイラーは「できない」と答えました。カギになったのは、地図を捨てたことです。大切なのは陸地と、その間の橋だけでした。陸地をそれぞれ点に、橋をそれぞれ線にしたのです。そして、そのような散歩ができるには、出発点と終点をのぞくすべての点に偶数本の線がつながっていなければならないことを示しました。ケーニヒスベルクでは、4つの陸地のどれにも奇数本の線がつながっていました。
A B C D E F
このユニットの例のグラフ。Aが出発点、Fがゴールです。辺：A‑B、A‑C、B‑D、C‑D、C‑E、D‑F、E‑F。

グラフをコードで表す

グラフを表すよくある方法は隣接リストです。頂点ごとに、隣の頂点のリストを持たせます。MITの6.006の講義ノートもまさにこれを使っていて、配列か辞書 Adj の Adj[u] に、uと結ばれた頂点を並べます。上のグラフなら次のようになります。

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

幅優先探索：輪を1つずつ

幅優先探索（BFS）は、出発点のまわりを輪のように広げながらグラフを調べます。まず距離0の出発点そのもの。次に距離1の、出発点の隣すべて。次にそれらの隣にある新しい頂点すべてで距離2、とこれを続けます。そのためにキューを使います。キューとは、最初に入ったものが最初に出る行列のことです。キューの先頭の頂点を取り出して訪問し、まだ見ていない隣の頂点を後ろに加えます。例のグラフでAから始めると、BFSはA、次にBとC、次にDとE、次にFを訪問します。輪を1つずつ外へ広げるので、BFSがある頂点に初めてたどりついたとき、辺の数がいちばん少ない道を見つけたことになります。たとえばFはAから3本の辺の先にあり、A、B、D、Fがその一例です。

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // 先入れ先出し
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

深さ優先探索：行けるところまで行き、それから戻る

深さ優先探索（DFS）は、迷路の中で片手を壁につけて進む人のようにふるまいます。1つの道をできるだけ深くたどります。行き止まりやもう見た場所に来たら、いちばん最近の分かれ道まで戻って次の選択肢を試します。キューではなく、後入れ先出しのスタックを使います。再帰で書くのがとても自然で、その場合は呼び出しスタックが覚えておく役をしてくれます。Aから始めると、再帰のDFSはA、B、D、C、E、Fの順に訪問します。DFSはBFSがたどりつくすべての頂点にたどりつきますが、たどる道がいちばん短いとは限りません。

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}
読み込み中

ドラッグで回転、スクロールまたはピンチで拡大・縮小。

グラフとしての迷路：通れるマスはそれぞれ頂点で、隣の通れるマスと結ばれています。同じ迷路でBFS、次にDFSを実行し、訪問したマスと見つけた道の長さを比べましょう。

どちらを使うか

ラボの最初の迷路では、BFSは105マスを訪問し、考えられるいちばん短い22手の道を見つけます。DFSはたまたまゴールのほうへ突き進み、訪問するのは31マスだけですが、その道は28手かかります。どちらかがいつも安上がりというわけではありません。どちらも各頂点と各辺を決まった回数だけ扱うので、V個の頂点とE本の辺に対して、どちらも O(V + E) 時間で動きます。いちばん少ない手数が必要なとき、たとえばパズルの最少の手数や、2人の間をつなぐ最少のつながりを知りたいときは、BFSを選びます。すべてを調べたいときや、選択を最後までたどりたいとき、たとえば迷路のすべての部屋がつながっているかを確かめたり、パズルの手を1筋ずつ試して行きづまったら戻ったりするときは、DFSを選びます。道路のように辺の長さがまちまちなときは、どちらだけでも足りません。ダイクストラ法のような方法が、BFSの考え方を距離つきに広げています。

どちらの探索も、もう見た頂点を覚えておかなければなりません。そうしないと、ループのあるグラフ（AからB、D、Cを通ってAに戻る）では、探索がいつまでもぐるぐる回ってしまいます。
グラフ辺で結ばれた頂点
頂点（ノード）グラフの点
辺2つの頂点を結ぶ線
隣接リスト頂点ごとの、隣の頂点のリスト
キュー先入れ先出し。BFSで使う
BFS幅優先探索：輪を1つずつ。辺の数が最少の道を見つける
DFS深さ優先探索：まず深く、それから戻る。スタックを使う
O(V + E)BFSとDFSの実行時間
  1. 例のグラフで、AからFへのいちばん短い道には辺が何本ありますか？
  2. 例のグラフには辺が何本ありますか？
  3. 幅優先探索が使うデータ構造はどれですか？
    • キュー（先入れ先出し）
    • スタック（後入れ先出し）
    • 整列したリスト
    • 何の構造も使わない
  4. 辺の数が最少の道を必ず見つけるのはどちらの探索ですか？
    • BFS
    • DFS
    • いつでも両方
    • どちらでもない
  5. Aから始めるBFSが頂点を訪問する順に並べましょう（隣はアルファベット順に取ります）。
  6. Aから始める再帰のDFSが頂点を訪問する順に並べましょう（隣はアルファベット順）。
  7. ラボの15×9のマス目で壁をすべて消したとき、S（左上）からG（右下）へのいちばん短い道は何手ですか？
  8. BFSとDFSが、もう見た頂点を覚えておかなければならないのはなぜですか？
    • そうしないと、グラフのループのせいで探索が永遠に回り続けるから
    • 最後に表示するため
    • 並べるため
    • DFSでだけ必要
  9. オイラーがケーニヒスベルクの橋の問題を解いたのは何年ですか？
    • 1683
    • 1736
    • 1843
    • 1945
  10. V個の頂点とE本の辺のグラフで、BFSの実行時間はどうなりますか？
    • O(V + E)
    • O(V × E)
    • O(log V)
    • O(2ⱽ)
  11. SNSで、2人の間をつなぐ「友だちの友だち」のつながりが最少で何本かを知りたいとします。どの探索を使いますか？
    • BFS
    • DFS
    • 二分探索
    • マージソート
ポイント
  • グラフは辺で結ばれた頂点。隣接リストで表す。
  • BFSはキューを使い、輪を1つずつ広げ、辺の数が最少の道を見つける。
  • DFSはスタック（または再帰）を使い、まず深く進んでから戻る。
  • どちらも O(V + E) で動き、もう見た頂点を覚えておく必要がある。
  • 1736年のオイラーによるケーニヒスベルクの橋の解決が、グラフ理論の始まり。
このコースの出典 (11)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
  • lecture notes 1 Introduction, 3 Sorting, 9 Breadth-First Search, 10 Depth-First Search (ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes) and Fall 2011 lecture 13 BFS notes (ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011)
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (MIT Press)
  • with the CLRS-based Khan Academy algorithms unit by Thomas Cormen and Devin Balkcom of Dartmouth (khanacademy.org/computing/computer-science/algorithms: binary search, selection sort analysis, merge sort, quicksort overview and analysis)
  • MacTutor History of Mathematics, Al-Khwarizmi (mathshistory.st-andrews.ac.uk/Biographies/Al-Khwarizmi: word algorithm from the Latin title Algoritmi de numero Indorum)
  • D. E. Joyce, Euclid's Elements Book VII Propositions 1 and 2 (mathcs.clarku.edu/~djoyce/elements/bookVII)
  • Wolfram MathWorld, Merge Sort (mathworld.wolfram.com/MergeSort.html: proposed by John von Neumann in 1945, after Knuth 1998 p. 159)
  • Stanford CS "Tony Hoare: Quicksort" (cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/quicksort.html: devised while a student at Moscow State University for Russian-English machine translation with a tape dictionary, programmed in Algol 60 and published 1961; the year 1959 from the Wikipedia Quicksort article and its cited sources)
  • Bodleian Libraries, Ada Lovelace (blogs.bodleian.ox.ac.uk/adalovelace: 1843 paper, Note G Bernoulli numbers)
  • Fourmilab text of Menabrea's Sketch with Lovelace's notes (fourmilab.ch/babbage/sketch.html)
  • Seven Bridges of Konigsberg (Euler 1736) and Tower of Hanoi (Edouard Lucas, 1883) checked against the Wikipedia articles and their cited sources.

確認日: 2026-10-17