Графы
Обход невзвешенного графа и кратчайшие пути с неотрицательными весами.
Вершин n, рёбер m.
- Списки смежности
- Поиск в ширину
- Поиск в глубину
- Алгоритм Дейкстры
Списки смежности
память O(n + m)
Для каждой вершины храним список соседей. У невзвешенного графа это номера вершин,
у взвешенного — пары «сосед, вес ребра». Перебрать все рёбра можно за O(n + m):
внешний цикл идёт по вершинам, внутренний — по их спискам, а сумма длин списков равна m
в ориентированном графе и 2m в неориентированном.
vector<vector<int>> g(n); // невзвешенный
vector<vector<pair<int, int>>> gw(n); // (сосед, вес)
// неориентированное ребро u—v
g[u].push_back(v);
g[v].push_back(u);
Поиск в ширину
время O(n + m)
память O(n)
BFS обходит граф слоями. В очередь сначала кладётся стартовая вершина, расстояние до неё равно 0.
Достаём вершину и смотрим ещё не посещённых соседей: каждому пишем расстояние на единицу больше
и ставим в хвост очереди. Каждая вершина попадает в очередь один раз, каждое ребро просматривается
константное число раз, поэтому время O(n + m).
В невзвешенном графе dist[v] — длина кратчайшего пути из старта в рёбрах.
Массив parent запоминает, откуда мы пришли, и по нему путь восстанавливается с конца.
Доказательство.
Индукция по расстоянию k. Для k = 0 в очереди только старт, и это верно.
Пусть все вершины на расстоянии меньше k уже получили правильное расстояние
и обработаны раньше вершин с большим расстоянием: очередь всегда хранит вершины
в порядке неубывания dist, потому что новые значения равны dist[u] + 1
и добавляются в конец. Тогда первая ещё не посещённая вершина на расстоянии k
обнаруживается из соседа на расстоянии k - 1. Более короткого пути нет:
любой путь длины меньше k заканчивался бы в уже обработанном слое.
Повторно вершину не ставим в очередь, иначе тот же слой разобрали бы несколько раз.
vector<int> bfs(const vector<vector<int>>& g, int start) {
const int inf = 1e9;
vector<int> dist(g.size(), inf);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[v] != inf) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
return dist;
}
Поиск в глубину
время O(n + m)
память O(n)
DFS уходит в первого непосещённого соседа и возвращается, только когда список соседей исчерпан.
Вершину красят в три цвета: белая — не видели, серая — зашли, но не вышли, чёрная — обработана.
tin[v] — время входа, tout[v] — время выхода. Ребро в серую вершину
замыкает цикл: на стеке рекурсии лежит путь из этой вершины в текущую. Чёрные вершины уже
лежат в своей компоненте обхода. Если запустить DFS из каждой белой вершины, получим все
компоненты связности неориентированного графа.
Доказательство полноты.
Каждая вершина красится в серый ровно один раз: белую мы красим при входе и больше не заходим.
Из серой вершины просматривается каждый её сосед. Если сосед белый, обход продолжается в него.
Значит, из стартовой вершины будут посещены все вершины, достижимые по рёбрам:
если бы осталась белая вершина v с путём из старта, на этом пути нашлось бы ребро
из уже чёрной или серой вершины в белую, и при обработке начала ребра мы обязаны были шагнуть дальше.
Рёбер конечное число, каждое смотрится один раз со стороны исходящей вершины, поэтому время O(n + m).
Глубина рекурсии в худшем случае O(n) — это и есть дополнительная память.
enum Color { White, Gray, Black };
int timer = 0;
vector<int> tin, tout;
vector<Color> color;
void dfs(const vector<vector<int>>& g, int u) {
color[u] = Gray;
tin[u] = timer++;
for (int v : g[u]) {
if (color[v] == White) dfs(g, v);
// color[v] == Gray — ребро в предка, в ориентированном графе это цикл
}
color[u] = Black;
tout[u] = timer++;
}
Алгоритм Дейкстры
O(n² + m) плотный граф
O(m log n) куча
веса ≥ 0
Нужны кратчайшие пути из одной вершины, веса рёбер неотрицательны.
dist[v] — длина лучшего уже известного пути в v. Сначала все расстояния
бесконечны, кроме старта. Пока есть необработанные вершины, берём ту, у которой dist минимален,
и пробуем улучшить соседей: если dist[u] + w < dist[v], записываем новую оценку
и запоминаем предка u.
Плотная реализация каждый раз за O(n) ищет минимум среди ещё не закрытых вершин
и делает это n раз, а каждое ребро ослабляется один раз: итог O(n² + m).
На разреженном графе минимум хранят в куче. Одно и то же ребро может положить в кучу несколько
устаревших пар, но вершина закрывается при первом извлечении, поэтому время O(m log n)
при бинарной куче.
Доказательство.
В момент, когда вершина u выбирается как минимум среди незакрытых, dist[u]
уже равно длине кратчайшего пути. Иначе у кратчайшего пути s → … → x → y → … → u
есть первое ребро x → y, где x уже закрыта, а y ещё нет.
После закрытия x оценка dist[y] не больше длины этого префикса.
Веса неотрицательны, поэтому префикс до y не длиннее всего пути до u,
и dist[y] ≤ dist[u]. Но u выбрана как вершина с минимальной оценкой,
значит dist[y] = dist[u] и хвост пути после y имеет нулевой вес.
Тогда и оценка u не улучшается: противоречие с тем, что она была строго больше
длины кратчайшего пути. Отрицательный вес ломает шаг «префикс не длиннее всего пути»,
поэтому алгоритм на таких рёбрах не применяют.
Плотный граф, O(n² + m)
vector<int> dijkstra_dense(
const vector<vector<pair<int, int>>>& g, int start) {
const int inf = 1e9;
int n = g.size();
vector<int> dist(n, inf);
vector<char> used(n);
dist[start] = 0;
for (int iter = 0; iter < n; ++iter) {
int u = -1;
for (int i = 0; i < n; ++i)
if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
if (u == -1 || dist[u] == inf) break;
used[u] = 1;
for (auto [v, w] : g[u])
dist[v] = min(dist[v], dist[u] + w);
}
return dist;
}
Разреженный граф, O(m log n)
vector<int> dijkstra(
const vector<vector<pair<int, int>>>& g, int start) {
const int inf = 1e9;
vector<int> dist(g.size(), inf), parent(g.size(), -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du != dist[u]) continue; // устаревшая пара в куче
for (auto [v, w] : g[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
return dist;
}
Путь в вершину t собирается по parent, пока не дойдём до старта, затем разворачивается.
Если parent так и остался -1 и t не старт, вершины недостижимы.