

### 質問

グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか？

深さ優先探索の場合、スタックか再帰関数を使って実装ができます。  
一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。

参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、実装をご教示くださると助かります。  
おそらく、bfs_visit(int
u)のような、uを訪れる関数を定義して、それらを再帰関数として使うのだろうと思っています。ですが、深さ優先探索とは違って、幅優先にさせるロジックをどう実装したらよいのかわかりません。

### 参考

この問題を再帰関数による幅優先探索で解こうとしています。キューを使った場合は、後述のソースコードで問題なくとおります。  
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp)

### キューを使った場合の幅優先探索の実装

(長いのでスクロールしてください)

[code]

    #include <iostream>
    #include <queue>
    #define NIL -1
    #define N 110
    
    using namespace std;
    
    bool A[N][N];
    int d[N];
    int n;
    
    void bfs(int s) {
      queue<int> q;
      for (int i = 0; i < N; i++) d[i] = NIL;
      q.push(s);
      d[s] = 0;
      while(!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < n; v++) {
          if (A[u][v] && d[v] == NIL) {
            q.push(v);
            d[v] = d[u] + 1;
          }
        }
      }
    }
    
    int main() {
    
      cin >> n;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          A[i][j] = false;
        }
      }
    
      for (int i = 0; i < n; i++) {
        int u, k, v;
        cin >> u >> k;
        u--;
        for (int j = 0; j < k; j++) {
          cin >> v;
          v--;
          A[u][v] = true;
        }
      }
    
      bfs(0);
    
      for (int i = 0; i < n; i++) {
        cout << i+1 << " " << d[i] << endl;
      }
    }
    
[/code]


CC BY-SA 4.0
2018-10-05T22:58:21.330
49009
2019-01-05T05:38:26.700
29267
question
c++ c アルゴリズム グラフ理論
幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか？


単純ループは簡単に再帰処理に書き直せるので、出来なくはないでしょう。それが自然かとか分かりやすいかとかは別にするのであれば。

[code]

    void fn(int start, int end) {
        for( int i = start; i < end; ++ i ) {
            cout << i << endl;
        }
    }
    
    void fr(int i, int end) {
        if( i >= end ) return;
        cout << i << endl;
        fr(i+1, end);
    }
    
[/code]

`fn(0, 10)`と`fr(0, 10)`は(スタック消費の深さとかを無視すれば)同じ動作になります。

* * *

キューを使わずと言うのがお題にあるので、ここでは距離nでたどり着ける頂点の一覧を`vector`で保持する、ってやり方で書いてみました。

あなたのコードで使われているデータ表現を、できるだけそのまま使うとこんな感じです。

[code]

    #include <iostream>
    #include <vector>
    #define NIL -1
    #define N 110
    
    using namespace std;
    
    bool A[N][N];
    int d[N];
    int n;
    
    void rbfs(const vector<int>& curr) {
        vector<int> next;
        for( int i = 0; i < curr.size(); ++i ) {
            int u = curr[i];
            for( int v = 0; v < n; ++v ) {
                if( A[u][v] && d[v] == NIL ) {
                    next.push_back(v);
                    d[v] = d[u] + 1;
                }
            }
        }
        if( !next.empty() ) {
            rbfs(next);
        }
    }
    
    int main() {
        cin >> n;
        for( int i = 0; i < n; ++i ) {
            for( int j = 0; j < n; ++j ) {
                A[i][j] = false;
            }
        }
    
        for( int i = 0; i < n; ++i ) {
            int u, k, v;
            cin >> u >> k;
            u--;
            for( int j = 0; j < k; ++j ) {
                cin >> v;
                v--;
                A[u][v] = true;
            }
        }
    
        for( int i = 0; i < N; ++i ) d[i] = NIL;
        const int s = 0;
        d[s] = 0;
        vector<int> start;
        start.push_back(s);
        rbfs(start);
    
        for( int i = 0; i < n; ++i ) {
            cout << i+1 << " " << d[i] << endl;
        }
    }
    
[/code]

(再帰の深さを表すパラメータを持たせれば、それがそのまま距離になるようになっているのですが、ここでは元の構造に近い書き方になるようにしています。その他細かい修正は自分の趣味ですので、全然本質には関係ありません。)

* * *

ただ、この部分:

[code]

            for( int v = 0; v < n; ++v ) {
                if( A[u][v] && d[v] == NIL ) {
                    next.push_back(v);
                    d[v] = d[u] + 1;
                }
            }
    
[/code]

頂点`u`からたどり着ける頂点`v`を探すのに、グラフ内の全頂点を全て舐めると言うのは効率が悪いですね。V×V→Boolのマトリックスで有向グラフを表現すると言うのは、理論的取扱いをするときには便利なこともありますが、今回のような探索問題には不向きです。

元の入力データに近いデータ構造を使った方が高速化できます。

[code]

    #include <iostream>
    #include <vector>
    #define NIL -1
    #define N 110
    
    using namespace std;
    
    vector<vector<int>> Arcs;
    int d[N];
    int n;
    
    void rbfs2(const vector<int>& curr) {
        vector<int> next;
        for( int i = 0; i < curr.size(); ++i ) {
            int u = curr[i];
            for( int j = 0; j < Arcs[u].size(); ++j ) {
                int v = Arcs[u][j];
                if( d[v] == NIL ) {
                    next.push_back(v);
                    d[v] = d[u] + 1;
                }
            }
        }
        if( !next.empty() ) {
            rbfs2(next);
        }
    }
    
    int main() {
        cin >> n;
        Arcs.resize(n);
    
        for( int i = 0; i < n; ++i ) {
            int u, k, v;
            cin >> u >> k;
            for( int j = 0; j < k; ++j ) {
                cin >> v;
                Arcs[u-1].push_back(v-1);
            }
        }
    
        for( int i = 0; i < N; ++i ) d[i] = NIL;
        const int s = 0;
        d[s] = 0;
        vector<int> start;
        start.push_back(s);
        rbfs2(start);
    
        for( int i = 0; i < n; ++i ) {
            cout << i+1 << " " << d[i] << endl;
        }
    }
    
[/code]

一応簡単な動作確認はしていますが、何かお気付きの点があれば、おしらせください。


CC BY-SA 4.0
2018-10-06T03:13:53.653
49011
2018-10-06T03:37:57.573
2018-10-06T03:37:57.573
13972
13972
49009
answer


幅優先探索では現在訪れているノードの兄弟を見つける必要がありますが、あるノードからは直接兄弟ノードが見えないので、再帰関数で書き換えるにしても何らかの補助的なデータ構造が必要になると思います。効率を考えるならばこれはキューになるでしょう。

しかし、効率を度外視して良いならば次のような方法もあります。すなわちDFS関数のパラメータとして興味のあるノードの深さを追加し、それをループごとに１ずつ増やしていくという方法です。更に言い換えるならば、ある`depth`を決めたときちょうど`depth`ステップでたどり着けるか判定するということです。これは厳密には幅優先探索とは言い難いですが、それと同等のことを行います。

ところでこれをそのまま実装したところTLEになってしまったので、以下のコードでは無駄なノード探索をしないようにしています。

[code]

    // 新しいノードが見つかったらtrue
    bool dfs(int u, int lv, int depth) {
      // 無駄な探索はしない
      if (d[u] >= 0 && d[u] < lv) return false;
      if (lv == depth) {
        if (d[u] == NIL) {
          d[u] = depth;
          return true;
        }
        return false;
      }
      else {
        bool r = false;
        for (int v = 0; v < n; v++)
          if (A[u][v]) r |= dfs(v, lv+1, depth);
        return r;
      }
    }
    
[/code]

`main`関数で`bfs(0);`の部分を次で置き換えます。

[code]

    for (int i = 0; i < N; i++) d[i] = NIL;
    int depth = 0;
    while (dfs(0,0,depth)) depth++;
    
[/code]

浅いところにあるノードを何度も訪れることになるので、効率としてはキューを使った場合に劣ります。


CC BY-SA 4.0
2018-10-06T05:41:39.087
49014
2018-10-06T05:41:39.087
13199
49009
answer


キューでなくともスタックと再帰関数で解けます。問題自体難しくないですので。

関数はスタックの仕組みで実現されるので再帰関数を使うとスタックの代替になります。ですが再帰関数とよく比較されるのはループです。（末尾再帰最適化の仕組みがない場合）再帰関数はネストを深くするとスタックオーバーフローするのでループを用います。再帰関数は木構造を探索するのに適しています。

[code]

    #include <iostream>
    #include <stack>
    #define NIL -1
    #define N 110
    
    using namespace std;
    
    bool A[N + 1][N + 1];
    int d[N + 1];
    int n;
    
    stack<int> s1;
    stack<int> s2;
    
    void bfs(int depth, stack<int> si, stack<int> so) {
      if (si.empty()) return;
      while (!si.empty()) {
        int u = si.top();
        si.pop();
        for (int v = 1; v <= n; v++) {
          if (A[u][v] && d[v] == NIL) {
            so.push(v);
            d[v] = depth;
          }
        }
      }
      bfs(depth + 1, so, si);
    }
    
    int main() {
    
      cin >> n;
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          A[i][j] = false;
        }
      }
    
      for (int i = 1; i <= n; i++) {
        int u, k, v;
        cin >> u >> k;
        for (int j = 1; j <= k; j++) {
          cin >> v;
          A[u][v] = true;
        }
      }
    
      for (int i = 1; i <= N; i++) d[i] = NIL;
      s1.push(1);
      d[1] = 0;
      bfs(1, s1, s2);
    
      for (int i = 1; i <= n; i++) {
        cout << i << " " << d[i] << endl;
      }
    }
    
[/code]


CC BY-SA 4.0
2019-01-05T05:38:26.700
51722
2019-01-05T05:38:26.700
31654
49009
answer