体系ガイド · 入門

BFSとDFSを、探索順と最短路から理解する

頂点と辺の表現、訪問済みの管理、重みの有無を確認し、目的に合うグラフ探索を選びます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 何を頂点と辺にするか決める
  2. BFSは、近い層から広げる
  3. DFSは、深く進んで戻る
  4. 重みがあるときと、計算量の限界
  5. この記事をロゲイアに質問する理解を確かめる

何を頂点と辺にするか決める

駅と路線、Webページとリンク、仕事と依存関係などは、グラフとして表せます。ただし、同じ対象でも辺の向きや重みの意味は設計によって変わります。「リンクがある」と「相互に移動できる」は同じではありません。まず、頂点が何を表し、どちらへ移動でき、何を最短にしたいかを定義します。

到達できるかだけを調べる問題と、辺の本数が最小の経路を探す問題と、所要時間の合計を最小にする問題は異なります。探索手法を選ぶ前に、目的と入力の条件を言葉にしましょう。存在しない頂点、孤立した頂点、自己ループ、同じ辺の重複も、入力として扱うか決めておきます。

BFSは、近い層から広げる

幅優先探索BFSでは、通常はキューを使って始点から近い層の頂点を先に処理します。すべての辺の移動コストが等しい場合、始点から通る辺の本数が最小の距離を求められます。頂点を初めてキューへ入れるときに発見済みとして記録すれば、同じ頂点を何度も追加するのを防げます。

例えば、AからBとCへ辺があり、CからBへも辺があるとします。AからのBの距離は1です。Cを後で調べてBを見つけても、Bを新しく追加し直す必要はありません。距離と前の頂点を記録しておけば、到達の判定に加えて、発見した経路を後から復元できます。

python
from collections import deque

def distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph.get(u, []):
            if v not in distance:
                distance[v] = distance[u] + 1
                queue.append(v)
    return distance

DFSは、深く進んで戻る

深さ優先探索DFSは、一つの枝を深くたどってから別の枝へ戻る進め方です。明示的なスタックや再帰で実装できます。到達性やグラフの構造を調べる用途に役立ちますが、最初に見つけた経路が、辺の本数の最小経路であるとは限りません。訪問済みの管理を忘れると、サイクルを巡って処理が終わらないこともあります。

再帰版では、グラフが深いと呼び出しスタックの制限にも注意が必要です。また、有向グラフのサイクル判定では、単に以前見た頂点かどうかだけではなく、現在の探索経路にいるかを区別する方法などを使います。目的ごとに、記録すべき状態が変わります。

重みがあるときと、計算量の限界

AからBへコスト5の辺、AからCへコスト1の辺、CからBへコスト1の辺があるとします。BFSは1本の辺でBに到達できますが、最小コストはCを通る2です。辺の本数の最小化と重み合計の最小化を区別し、非負の重みならDijkstra法などを検討します。負の重みを許す場合は、さらに条件に合う方法が必要です。

隣接リストで各頂点と辺を必要な回数だけ扱う基本的なBFSやDFSは、O(V+E)と説明できます。隣接行列で全列を毎回調べる実装では、同じ説明をそのまま当てはめられません。表現、入力の大きさ、到達範囲、補助メモリまで含めて、計算量を確認しましょう。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ