実装コラム 非再帰 DFS
深さ優先探索（ DFS ）は再帰関数を使うことで容易に実装することができます。（逆に、幅優先探索では再帰関数がほとんど役に立ちません。）一方で、再帰関数を実装するとローカル変数やプログラムポインタを暗黙的にメモリのスタック領域に積むことになり、メモリ効率的に無駄が生じる可能性があります。とくに Windows では ulimit -s unlimited ができず、コンパイル時に設定したスタックサイズでは巨大なグラフの探索で使い切ることがあります。このように再帰関数を用いない DFS が優れている面があります。（とりあえずそういうことにしてくれ…）
あまり適さない方法の 1 つは、再帰関数で生成されるスタックを自力で実装してしまうことです。結局、プログラムポインタ相当の値とローカル変数のバックアップをスタックにすべて積めばたいていの再帰関数をシミュレートできます。実装難易度や実行時パフォーマンスに難があります。
例：
void dfs(){
vector<int> st = STARTING_STATE;
while(!st.empty()){ // 再帰スタックが空になるまで
int programPtr = st.back(); st.pop_back();
switch(programPtr){
case A : {
int localVal1 = st.back(); st.pop_back(); // ローカル変数を復元
// ...
st.push_back(localVal1);
st.push_back(B); // 次の実行位置
} break;
// ...
}
}
}
またもう 1 つの方法は、探索候補を stack に逆順に積んでいくことで、幅優先探索と同様のアルゴリズムで探索する場合です。”明示的なグラフ”以外の探索など、この方法が適している場合もありそうですが、この方法の難点は、帰りがけの処理が非常に難しいことです。
例：
void dfs(){
vector<int> st = {s};
while(!st.empty()){ // 再帰スタックが空になるまで
int v = st.back(); st.pop_back();
if(visited(v)) continue;
visit(v);
for(int w : Adj[v].reversed()) st.push_back(w);
}
}
ここで本命を紹介します。
探索対象は明示的に与えられたグラフなので、探索する空間が $\lbrace 0,1,\ldots ,n-1 \rbrace$ に絞られています。だから、各呼び出し階層でスタックに積まれる情報を、探索している頂点に対応するメモリに書き込めばよいのです。このようにして得られるアルゴリズムを次に示します。
void dfs(){
vector<int> parent_vis(n, -1); // DFS 木上の親
vector<AdjIterator> ei; // 各頂点の隣接リストのイテレータ
for(int i=0; i<n; i++) ei.push_back(Adj[i].begin());
int v = s; // 探索中の頂点
parent_vis[v] = -2;
while(v >= 0){
if(ei[v] == Adj[v].begin()){
// 行きがけ
}
if(ei[v] == Adj[v].end()){
// 帰りがけ
v = parent_vis[v];
continue;
}
int w = ei[v]->to;
ei[v]++;
if(parent_vis[w] != -1){
// 後退辺
continue;
}
// DFS 木の辺
parent_vis[w] = v;
v = w;
}
}
これかなりメモリ効率良くないですか？ライブラリ盆栽に最適だと思います。
また、探索中の頂点 v 以外にプログラムポインタ ret をもって適切に改造すると、 Dinic 法における DFS のような挙動も表現できます。私がやったときは実行時のパフォーマンスがあまりよくなかったですが。