Алгоритмы

Графы

Обход невзвешенного графа и кратчайшие пути с неотрицательными весами. Вершин n, рёбер m.

  1. Списки смежности
  2. Поиск в ширину
  3. Поиск в глубину
  4. Алгоритм Дейкстры

Списки смежности

память 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 не старт, вершины недостижимы.