Восстановление кратчайшего пути после BFS: как хранить предков и не перепутать порядок?
BFS находит длину кратчайшего пути в невзвешенном графе, но мне нужен сам путь — последовательность вершин от старта до финиша. Как правильно хранить предков во время BFS и восстановить путь, чтобы он шёл в нужном порядке (от старта к финишу, а не наоборот)?
2 ответа
Заводим массив par[] — родитель каждой вершины в BFS-дереве. Когда впервые попадаем в u из v, ставим par[u] = v. Поскольку BFS даёт кратчайшие пути, дерево предков кодирует кратчайший путь до каждой вершины.
vector<int> bfsPath(int s, int t, int n, vector<int> g[]) {
vector<int> par(n, -1), dist(n, -1);
queue<int> q; q.push(s); dist[s] = 0;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : g[v]) if (dist[u] == -1) {
dist[u] = dist[v] + 1;
par[u] = v;
q.push(u);
}
}
if (dist[t] == -1) return {}; // пути нет
vector<int> path;
for (int v = t; v != -1; v = par[v]) path.push_back(v);
reverse(path.begin(), path.end()); // получили t..s, разворачиваем
return path; // теперь s..t
}
Ключевой момент порядка: идя по par[] от t, мы собираем путь задом наперёд (t, ..., s). Поэтому в конце reverse. Старт распознаём по par[s] == -1 (его никто не назначил), на нём цикл for останавливается.
Сложность O(V+E), восстановление O(длины пути) ≤ O(V), память O(V).
Грабля: помечайте par[u] в момент первого посещения (когда dist[u]==-1), а не при каждом просмотре ребра — иначе перезапишете оптимального предка более поздним и путь перестанет быть кратчайшим.
Тот же приём работает для Дейкстры (взвешенный граф): обновляете par[u] = v ровно тогда, когда делаете успешную релаксацию dist[u] = dist[v] + w. Восстановление и reverse — идентичны.
Если путей много и нужно считать число кратчайших путей (а не один), вместо par ведите cnt[u] — число кратчайших путей до u: при dist[v]+1 == dist[u] делаете cnt[u] += cnt[v] (по модулю, если просят). Это частый поворот задачи: «найди длину И количество кратчайших путей». А если нужен лексикографически минимальный путь — при равных расстояниях выбирайте предка с меньшим номером, перебирая соседей в отсортированном порядке.