Как найти кратчайший путь в невзвешенном графе через BFS и почему именно он даёт минимум рёбер?
Есть граф из n вершин, рёбра без весов. Нужно найти минимальное число рёбер от вершины s до всех остальных. Я знаю DFS, но он почему-то даёт не минимум. Как правильно сделать BFS и почему он гарантирует кратчайший путь?
2 ответа
В невзвешенном графе «кратчайший путь» = минимальное число рёбер. BFS обходит вершины слоями: сначала все на расстоянии 0, потом 1, потом 2 и т.д. Когда вершина впервые извлекается из очереди, она уже найдена по кратчайшему пути — потому что любой более длинный путь добрался бы до неё позже (в более дальнем слое). DFS же лезет вглубь и может дойти до вершины окольной дорогой раньше, чем по короткой.
vector<vector<int>> g(n);
vector<int> dist(n, -1); // -1 = не посещена
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : g[v]) if (dist[u] == -1) {
dist[u] = dist[v] + 1;
q.push(u);
}
}
Сложность O(V + E) по времени, O(V) по памяти. Каждая вершина кладётся в очередь ровно один раз (проверка dist[u] == -1), каждое ребро просматривается один раз.
Ключевой момент — помечать вершину посещённой в момент добавления в очередь, а не в момент извлечения. Если ставить dist только при извлечении, одна вершина может попасть в очередь несколько раз, и сложность раздуется. В коде выше dist[u] ставится сразу при push, поэтому каждая вершина в очереди максимум один раз.