Привет всем! помогите мне реализовать BFS при помощи рекурсии... очень нужно! **** **** это без рекурсии...

vector < vector > g; // граф int n; // число вершин int s; // стартовая вершина (вершины везде нумеруются с нуля)

// чтение графа ... Сам обход:

queue q; q.push (s); vector used (n); vector d (n), p (n); used[s] = true; p[s] = -1; while (!q.empty()) { int v = q.front(); q.pop(); for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) { used[to] = true; q.push (to); d[to] = d[v] + 1; p[to] = v; } } } Если теперь надо восстановить и вывести кратчайший путь до какой-то вершины , это можно сделать следующим образом:

if (!used[to]) cout << "No path!"; else { vector path; for (int v=to; v!=-1; v=p[v]) path.push_back (v); reverse (path.begin(), path.end()); cout << "Path: "; for (size_t i=0; i<path.size(); ++i) cout << path[i] + 1 << " "; }