幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?
質問
グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか?
深さ優先探索の場合、スタックか再帰関数を使って実装ができます。
一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。
参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、実装をご教示くださると助かります。
おそらく、bfs_visit(int u)のような、uを訪れる関数を定義して、それらを再帰関数として使うのだろうと思っています。ですが、深さ優先探索とは違って、幅優先にさせるロジックをどう実装したらよいのかわかりません。
参考
この問題を再帰関数による幅優先探索で解こうとしています。キューを使った場合は、後述のソースコードで問題なくとおります。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
キューを使った場合の幅優先探索の実装
(長いのでスクロールしてください)
#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;
}
}