グラフ探索アルゴリズム:深さ優先探索と幅優先探索

グラフを探索するアルゴリズム深さ優先探索幅優先探索
英語でいうと Depth-first Search (DFS)、Breadth-first Search (BFS)。

競技プログラミング頻出のアルゴリズム(基礎レベル?)ですが、知らないと自力でひらめくのは難しいはず。いわゆる”知識”として押さえておきたいアルゴリズムの一つ。

自分にとっての備忘のためと、「競技プログラミング始めたよ!」という人のため、アルゴリズムを実装した Python スクリプトと、簡単な解説を公開します。

from collections import deque

graph = [[None] * n for _ in range(n)]
reached = [False for _ in range(n)]

d = deque()
d.append(0)
reached[0] = True

for _ in range(n):
    v = d.pop()
    for i, e in enumerate(graph[v]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        d.append(i)
    if not d:
        break

こちらが深さ優先探索スクリプトです。

    v = d.pop()

    v = d.popleft()

にすると、幅優先探索になります。

グラフの初期化処理は割愛しています。
もし入れるとしたら変数の宣言箇所から考えてこの辺りになります。

graph = [[None] * n for _ in range(n)]
reached = [False for _ in range(n)]

    <<<<ココ

d = deque()
d.append(0)

適宜問題に合わせて柔軟に書き換えてください。

このままだと本当にグラフの各ノードを辿るだけで終わってしまいます。競技プログラミングで求められる「グラフを辿りながら、何かを数えたり、何かを更新したりする」場合は

    for i, e in enumerate(graph[v]):
        if e == None or reached[i]:
            continue
ココ>>>>
        reached[i] = True

reaced[i] = True の一行上に、for ループ直下のスコープで処理を入れてください。*1 *2

一行ずつスクリプトを追っていってみましょう。

from collections import deque

Python の deque クラスをインポートします。
以下は公式ドキュメントからの引用です。重要なのは太字にした箇所です。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

graph = [[None] * n for _ in range(n)]
reached = [False for _ in range(n)]

グラフ構造を表現する二次元リストと、到達済みノードを表現する一次元リストを宣言します。
graph を list の dict*3 や set の dict*4 にしてもよいですし、reached を set にしても動きますが、体感的に TLE になることが多いです。原因は謎です。*5

d = deque()

deque をインスタンス化します。

d.append(0)
reached[0] = True

探索を開始するノード(に該当するインデックス番号)を deque に追加し、到達済みであることを示すフラグを立てます。

for _ in range(n):
    v = d.pop()
    for i, e in enumerate(graph[v]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        d.append(i)

深さ優先探索の場合、deque の末尾に追加されているノードを調べます。幅優先探索の場合は deque の先頭のノードを調べます。
deque から取り出したノードについて、そのノードから他のノードへの辺が存在するどうか、そして辺が存在するならば到達済みか未到達かを評価します。
辺が存在しない、もしくは到達済みの場合は無視(continue)します。未到達の場合はそのノードを到達済みにし deque の末尾に追加します。

    if not d:
        break

deque の中に要素がなくなったら、探索を終了します。グラフが連結である場合、すべてのノードを探索できているはずです。逆にこれを用いてグラフが連結かどうかを判定することも可能ですが、Union-find を使った方がよい場合が多い感じがします。

以上、DFS と BFS の Python スクリプトとその解説でした。

(追記)続きました。

katoufujibanana.hatenadiary.jp

*1:中の if reached[i]: 下のスコープではないことに注意!

*2:問題によってはここ以外に処理を入れることもあるので、そこは臨機応変に。

*3:{[k: [] for k in range(n)]}

*4:{[k: set() for k in range(n)]}

*5:メモリを確保し直したりしてしまうとか? 誰かお詳しい方教えてください。