グラフ探索アルゴリズム:深さ優先探索の行きがけと帰りがけ

グラフを探索するアルゴリズム深さ優先探索。英語でいうと Depth-first Search (DFS)。深さ優先探索にはタイトルの通り、行きがけと帰りがけのバリエーションがあります。

前回の記事では Python の deque クラスを使用した、深さ優先探索幅優先探索の実装を公開しました。 前回の実装は行きがけのスクリプトとなります。

今回は行きがけの深さ優先探索と、帰りがけの深さ優先探索を表現するスクリプトをご用意いたしました。

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

import sys
sys.setrecursionlimit(1000000)


def dfs(n, graph, reached):
    for i, e in enumerate(graph[n]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        dfs(i, graph, reached)


def main():
    graph = [[None] * n for _ in range(n)]
    reached = [False for _ in range(n)]
    reached[0] = True

    dfs(0, graph, reached)

今回のスクリプトでは、関数の再帰呼び出しを使います。

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

import sys
sys.setrecursionlimit(1000000)

Python の sys モジュールをインポートし、setrecursionlimit メソッドを実行します。
Python は関数の再帰呼び出しを行う際、呼び出せる回数に制限がかけられています。この制限を設定できるのが、sys.setrecursionlimit メソッドです。
setrecursionlimit の引数には、呼び出せる回数の上限を渡してください。問題にもよりますが、 10^{6} もあれば十分です。*1

def main():
    graph = [[None] * n for _ in range(n)]
    reached = [False for _ in range(n)]
    reached[0] = True

    dfs(0, graph, reached)

先に、main 関数を見ます。
二次元リスト表現の graph と到達済みノードの格納リストを宣言し、探索開始ノード(ここでは 0 番ノード)の到達済みフラグを立てています。 最後に dfs 関数を呼び出し、探索を開始します。

def main():
    graph = [[None] * n for _ in range(n)]
ココ>>>>
    reached = [False for _ in range(n)]
    reached[0] = True
ココ>>>>

    dfs(0, graph, reached)

グラフの初期化を行うのは、この2か所のどちらかになると思います。

def dfs(n, graph, reached):
    for i, e in enumerate(graph[n]):
        if e == None or reached[i]:
            continue
        reached[i] = True
        dfs(i, graph, reached)

最後に dfs 関数です。n は現在見ているノードの番号です。graph と reached はそれぞれ main 関数から呼び出す際に渡した、グラフと到達済みノードを表すリストです。
前回と同じように、まずは他のノードへの辺が存在するどうか、そして辺が存在するならば到達済みか未到達かを評価します。
辺が存在しない、もしくは到達済みの場合は無視(continue)します。未到達の場合はそのノードを到達済みにし、第一引数をそのノードの番号にして再帰的に dfs 関数を呼び出します。

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

行きがけに探索する場合は、ここに処理を入れてください。

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

帰りがけの場合は、ここに処理を入れてください。

以上、行きがけの深さ優先探索と、帰りがけの深さ優先探索Python スクリプトとその解説でした。

*1:ノードの個数、つまり n あれば十分です。気持ちそれより多めに、2 * n とかでよいかもしれません。