Остовные деревья

Задача о минимальном остове

Рассмотрим следующую задачу:

Авиакомпания обслуживает \(m\) рейсов между \(n\) городами. Содержание \(i\)-го рейса стоит \(w_i\) рублей, и из любого города можно добраться до любого другого. Во время кризиса нужно оставить такой набор рейсов, чтобы связность сохранилась, а суммарная стоимость оставшихся рейсов была минимальной.

Если рассматривать города как вершины, а рейсы как рёбра неориентированного взвешенного графа, то задача сводится к поиску подграфа минимального суммарного веса, который

содержит все вершины;
остается связным.

Почему ответ обязательно будет деревом?

Если в выбранном подграфе есть цикл, то из него можно удалить любое ребро и не нарушить связность. Значит, в оптимальном ответе циклов быть не может.
Если подграф несвязен, то он просто не удовлетворяет условию задачи.

Итак, мы ищем остов графа, то есть связный ациклический подграф на всех вершинах. Среди всех остовов нас интересует тот, у которого суммарный вес минимален. Такой объект называется минимальным остовом. По-английски это minimum spanning tree (MST).

В этой мы разберем общую жадную идею для поиска MST и два классических алгоритма: Прима и Борувки.

Лемма о безопасном ребре

Назовем подграф \(T\) графа \(G\) безопасным, если он содержится хотя бы в одном минимальном остове графа \(G\).

Ребро \(e\) будем называть безопасным для \(T\), если подграф \(T \cup \{e\}\) тоже безопасен.

Разрезом графа назовем разбиение множества его вершин на две непустые части. Ребро пересекает разрез, если его концы лежат в разных частях. Будем говорить, что разрез согласован с \(T\), если ни одно ребро из \(T\) этот разрез не пересекает.

Все стандартные алгоритмы поиска минимального остова опираются на следующее утверждение.

Лемма о безопасном ребре. Пусть \(T\) — безопасный подграф, а разрез согласован с \(T\). Тогда любое ребро минимального веса среди рёбер, пересекающих этот разрез, безопасно для \(T\).

Доказательство. Рассмотрим минимальный остов \(M\), который содержит \(T\). Если выбранное ребро \(e\) уже лежит в \(M\), то доказывать нечего. Иначе добавим \(e\) в \(M\). Тогда появится цикл, и на этом цикле найдется ребро \(f\), которое тоже пересекает тот же разрез. Так как разрез согласован с \(T\), ребро \(f\) не принадлежит \(T\). Поскольку \(e\) имеет минимальный вес среди рёбер, пересекающих разрез, имеем \(w(e) \le w(f)\). Значит, если удалить из полученного цикла ребро \(f\), то снова получится остов веса не больше, чем у \(M\). Но \(M\) уже минимален, значит новый остов тоже минимален и при этом содержит \(T \cup \{e\}\). Следовательно, ребро \(e\) безопасно. ∎

Из этой леммы следует общая жадная стратегия: если на каждом шаге мы добавляем ребро, которое является минимальным для некоторого согласованного разреза, то мы не теряем возможность достроить решение до минимального остова.

Следствия

Если все веса рёбер различны, то минимальный остов единственен.
Если все веса положительны, то минимальный остов одновременно минимизирует и произведение весов рёбер. Для этого достаточно заменить веса на их логарифмы.
Любой минимальный остов также минимизирует вес самого тяжелого ребра среди всех остовов.

Алгоритм Прима

Алгоритм Прима строит минимальный остов постепенно. Мы поддерживаем множество уже выбранных вершин и на каждом шаге присоединяем к нему одну новую вершину самым дешевым возможным ребром.

Почему это корректно? В каждый момент выбранные вершины и остальные вершины образуют разрез, согласованный с уже построенной частью остова. Значит, минимальное ребро, выходящее наружу, безопасно.

Алгоритм выглядит так:

Возьмем произвольную стартовую вершину.
Пока в остов не вошли все вершины, будем выбирать ребро минимального веса, у которого один конец уже в остове, а другой еще нет.
Добавим это ребро и новую вершину в остов.

По идее это очень похоже на алгоритм Дейкстры: там мы тоже постепенно расширяем множество «готовых» вершин, но выбираем следующую вершину по другой величине. В Дейкстре это кратчайшее расстояние от источника, а здесь — вес минимального ребра, которым можно присоединить вершину к текущему остову.

Совсем наивная реализация работает за \(O(nm)\): на каждом шаге мы просто перебираем все рёбра и ищем лучшее ребро, расширяющее текущий остов.

const int maxn = 1e5, inf = 1e9;
vector<int> from, to, weight;
bool used[maxn];

// Считываем рёбра в массивы from/to/weight.
// Для неориентированного графа каждое ребро удобно занести в обе стороны.

used[0] = true;
for (int i = 0; i < n - 1; i++) {
    int opt_w = inf, opt_from = -1, opt_to = -1;
    for (int j = 0; j < m; j++)
        if (opt_w > weight[j] && used[from[j]] && !used[to[j]])
            opt_w = weight[j], opt_from = from[j], opt_to = to[j];

    used[opt_to] = true;
    cout << opt_from << " " << opt_to << endl;
}

Можно сделать лучше, если для каждой вершины хранить вес минимального ребра, которым ее сейчас можно присоединить к уже построенной части остова. Тогда следующую вершину мы будем выбирать по этому значению.

Такая реализация работает за \(O(n^2)\):

const int maxn = 1e5, inf = 1e9;
bool used[maxn];
vector<pair<int, int>> g[maxn];
int min_edge[maxn], best_edge[maxn];

fill(min_edge, min_edge + n, inf);
min_edge[0] = 0;

// ...

for (int i = 0; i < n; i++) {
    int v = -1;
    for (int u = 0; u < n; u++)
        if (!used[u] && (v == -1 || min_edge[u] < min_edge[v]))
            v = u;

    used[v] = true;
    if (v != 0)
        cout << v << " " << best_edge[v] << endl;

    for (auto e : g[v]) {
        int u = e.first, w = e.second;
        if (!used[u] && w < min_edge[u]) {
            min_edge[u] = w;
            best_edge[u] = v;
        }
    }
}

Наконец, линейный поиск вершины можно заменить приоритетной очередью или set. Тогда получаем реализацию за \(O(m \log n)\):

set<pair<int, int>> q;
int min_edge[maxn], best_edge[maxn];

fill(min_edge, min_edge + n, inf);
min_edge[0] = 0;
q.insert({0, 0});

while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());

    if (used[v])
        continue;
    used[v] = true;

    if (v != 0)
        cout << v << " " << best_edge[v] << endl;

    for (auto e : g[v]) {
        int u = e.first, w = e.second;
        if (!used[u] && w < min_edge[u]) {
            q.erase({min_edge[u], u});
            min_edge[u] = w;
            best_edge[u] = v;
            q.insert({min_edge[u], u});
        }
    }
}

При этом реализацию за \(O(n^2)\) не стоит забывать: на плотных графах она часто оказывается не хуже, а иногда и лучше варианта с приоритетной очередью.