スタック変数を使った深さ優先探索と、再帰の違いについて

前提

再帰を使ったDFSはスタックに書き換えることができるそうですが、再帰の戻り値を使ったDFSをスタックによるDFSへの書き換え方がわかりません。

C++
1// 適当な例です
2struct node
3{
4	int value;
5	node *left;
6	node *right;
7};
8
9int dfs( node *n )
10{
11	if( n == nullptr )
12		return INT_MIN;
13
14	int left_value = dfs( n->left );
15	int right_value = dfs( n->left );
16	
17	return max( n->value, max( left_value, right_value ));
18}

例えばこのようなグラフ探索のコードがあるとします。左右の子ノードを探索し、自身の値を含めた3つの中で最大の値を呼び出し元に返すことを意識しています。

これをスタック変数を使って書き換えると次のようになると思ったのですが

C++
1int main()
2{
3    struct node
4    {
5    	int value;
6    	node *left;
7    	node *right;
8    };
9    
10    stack<node> s;
11    node n;
12    s.push(n);
13    
14    while( !s.empty() )
15    {
16    	n = s.top();
17    	s.pop();
18    	
19    	if( n == nullptr )
20    		continue; // 次の状態をスタックに積まずにループを周回する
21    	
22		s.push(n->left);
23		s.push(n->right);
24    }
25}

この2つは動作が同じではないように思います。

再帰を使ったものは、A -> B -> Cという順で呼び出した場合にA -> B -> C -> B -> Aという順で遷移します。Bで再帰関数を呼び出した際にBの動作は一旦停止し、Cが終わってからBの続きをします。ですからBでCの結果を利用することができます。

しかしスタック変数の場合はループの中でスタックに積みますが、実際にノードを探索するのは次のループでスタックからpopしたときです。BでCをスタックに積みますが、Bが終わって次のループの冒頭でCがスタックからポップされます。ですから、BでCの結果を利用することはできないように思います。

これは例ですので、単に全ノードで一番大きな値が欲しいだけなら、どこかスコープの外で変数を宣言し、そこに格納すればいいのですが、細部で異なります。

DFSの場合は困ったら再帰でいいのですが、スタック変数とループの場合はスタックをキューに変更すれば、BFSに直せる点でメリットがあると考えています。

実現したいこと

再帰を使ったDFSを、スタック変数とループを使った等価なDFSに書き換えたい。

例えば

https://leetcode.com/problems/binary-tree-maximum-path-sum/

この問題を再帰を使わないで解きたい。

補足情報（FW/ツールのバージョンなど）

よろしくお願いします。

maisumakun

2022/08/16 01:05

> 細部で異なります。そのとおりです、としか言いようがないのですが、質問は何でしょうか？

行動規範の内容に同意します

回答2件

この場合、再帰と同じ動作にするためにスタックに積むのは、node だけでは足りません。状態を復帰するためのすべての情報を積む必要があります。おそらく、

node へのポインタなど
計算過程のフラグ; left_value を計算するとこなのか、right_value を計算するところなのか
left_value の値

の組をスタックに積んで、正しく状態を復帰させる必要があります。

もしnodeが親へのポインタを持っているとより簡単にループに変更できます。

投稿2022/08/16 01:41

int32_t

総合スコア21929

Hindenburg

2022/08/16 01:46

ありがとうございます。ちょうど入れ違いで補足を追加しました。ある問題（リンクは本文にあります）を解いていて、再帰では解けました。練習のために再帰を使わないで解こうとしたところ手が止まって、しばらく考えてもできませんでした。与えられたデータ型には親へのポインタはないので、別のデータ構造に変換する必要があるのかも知れません。

行動規範の内容に同意します

ベストアンサー

int32_t さんの回答をもとに「実現したいこと」のリンク先の問題を実装すると、以下のようになります。

c++
1struct node
2{
3    int value;
4    node* left;
5    node* right;
6};
7
8int dfs(node* n){
9    int left_value, right_value, maximum = INT_MIN, return_value, flag = 0;
10    stack<tuple<node*, int, int>> s;
11    s.push({ nullptr, 0, -1 });
12    while (!s.empty()) {
13        switch (flag) {
14        case 0:
15            if (n == nullptr) {
16                return_value = 0;
17                tie(n, left_value, flag) = s.top();
18                s.pop();
19                continue;
20            }
21            s.push({ n, left_value, 1 });
22            n = n->left;
23            flag = 0;
24            break;
25        case 1:
26            left_value = return_value;
27            s.push({ n, left_value, 2 });
28            n = n->right;
29            flag = 0;
30            break;
31        case 2:
32            right_value = return_value;
33            return_value = n->value + max({ 0, left_value, right_value });
34            maximum = max({ maximum, return_value, left_value + right_value + n->value });
35            tie(n, left_value, flag) = s.top();
36            s.pop();
37            break;
38        }
39    }
40    return maximum;
41}

再帰を使ったDFSはスタックに書き換えることができるそうですが、再帰の戻り値を使ったDFSをスタックによるDFSへの書き換え方がわかりません。

「再帰関数は再帰呼び出しの代わりにスタックを用いて書き直すことができる」という話と、「DFSには再帰を使ったものとスタックを使ったものがある」という話がごっちゃになって、「再帰を使ったDFSを、スタックを使ったDFSに書き直すことができる」と勘違いしているように思えます。

再帰を使ったDFSをスタックを用いて書き直すことはできますが(上記ソース)、それは「スタックを使ったDFS」とは別物なので、単純にスタックをキューにするだけでBFSに変更することはできません。

そもそも、自身の値の計算に再帰の戻り値を使うということは、子要素の計算が終わらないと結果が確定しないということなので、子要素の計算を後回しにするBFSに変換するのは無理があります。

あと一応、DFSでたどった経路を全部保存して、後から逆順にたどるという手もあります。
こちらなら、スタックをキューにしても正しい回答が返ります。
ただ、これだとDFSではなく「DFSの逆順」にたどっていることになるのではないでしょうか。

c++
1int dfs(node* n){
2    vector<node*> v;
3    stack<node*> s;
4    s.push(n);
5    while (!s.empty()) {
6        n = s.top();
7        s.pop();
8        if (n == nullptr)
9            continue;
10        v.push_back(n);
11        s.push(n->left);
12        s.push(n->right);
13    }
14
15    int maximum = INT_MIN;
16    unordered_map<node*, int> m;
17    m[nullptr] = 0;
18
19    for (auto i = v.rbegin(); i != v.rend(); ++i) {
20        n = *i;
21        int left_value = m[n->left];
22        int right_value = m[n->right];
23        m[n] = n->value + max({ 0, left_value, right_value });
24        maximum = max({ maximum, m[n], left_value + right_value + n->value });
25    }
26    return maximum;
27}