グラフ探索アルゴリズム:深さ優先探索の帰りがけ deque 実装版

以前の記事で、deque を使った深さ優先探索と幅優先探索の python スクリプトや、再帰関数をつかった深さ優先探索の行きがけと帰りがけの python スクリプトをご紹介しました。

deque による深さ優先探索は、前回の記事では行きがけの実装のみの記載となっておりました。今回は deque を使った深さ優先探索の帰りがけの実装をご紹介します。

というのも ABC209 の D - Collision の問題で PyPy3 で再帰深さ優先探索を提出したら TLE してしまいまして...。その場で deque 版を実装したのが経緯です。

こちらが、deque 版深さ優先探索の帰りがけのスクリプトとなります。

from collections import deque

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

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

r = deque()
r.append(0)

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

len_r = len(r)
for _ in range(len_r):
    i = r.pop()


行きがけの際のスクリプトから増えたのは、この3か所です。

r = deque()
r.append(0)
        r.append(i)        
len_r = len(r)
for _ in range(len_r):
    i = r.pop()


実際に帰りがけ順に処理を行う場合は、ココに処理を入れてください。

len_r = len(r)
for _ in range(len_r):
    i = r.pop()
        <<<<  ココ


処理の流れとしてはとくに難しいこともないかと思います。

d = deque() と同じように、もう一つの deque として r = deque() を用意しておき、探索の際に d と同じように r にもノードのインデックスを append していきます。

探索が終わるころには、r には d に append した順番と同じ順番でノードのインデックスが格納されています。探索の途中で d は pop によってデータが無くなってしまいますが、r にはデータが残ったままになっています。

r に探索対象のインデックスがすべて追加されたならば、r に pop を繰り返すことで、r に append された順番と逆の順番でインデックスを取り出し再探索します。r には d で探索した時の順番、つまり行きがけ順にインデックスが append されていたため、その逆の順番でインデックスを取り出すとその順番は帰りがけ順となります。


問題によっては、dp テーブルなど用意したうえで帰りがけ順の深さ優先探索をすることもあるかもしれません。その場合は適宜 dp テーブルの定義と遷移を差し込んでください。