幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか？


### 質問

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

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

参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、実装をご教示くださると助かります。  
おそらく、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]




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

[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]

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

