Алгоритм Крускала

Дано зважений неорієнтований граф. Потрібно знайти таке піддерево цього графа, яке б з'єднувало всі його вершини, і при цьому мало найменшу вагу (сум ваг ребер) з усіх можливих. Таке піддерево називається мінімальним каркасним деревом (MST) або просто мінімальним каркасом.

Властивості мінімального каркасу

• Мінімальний каркас унікальний, якщо ваги всіх ребер різні. В іншому випадку, можле існувати декілька мінімальних каркасів (алгоритми зазвичай отримують один з можливих каркасів).
• Мінімальний каркас є також і каркасом з мінімальним добутком ваг ребер. (доводиться заміною ваг всіх ребер на їх логарифми)
• Мінімальний каркас є також і каркасом з мінімальною вагою найважчого ребра.
• Каркас максимальної ваги шукається аналогічно каркасу мінімального ваги, достатньо поміняти знаки всіх ребер на протилежні і виконати будь-який з алгоритмів пошуку мінімального каркасу.

Алгоритм

Даний алгоритм був описаний Крускалом (Kruskal) в 1956 р.

Алгоритм Крускала спершу розташовує кожну вершину в своє незалежне дерево (розміром в одну вершину), а потім поступово об'єднує ці дерева, об'єднуючи на кожній ітерації два деяких дерева деяким ребром. Перед початком виконання алгоритму, всі ребра впорядковано по зростанню ваги. Потім починається процес з'єднання: перебираются всі ребра від першого до останнього (в порядку сортування), і якщо у поточного ребра його кінці належать різним деревам, то ці дерева об'єднуються, а ребро додається до відповіді. При закінченні перебору всіх ребер всі вершини опиняться в одному дереві, яке і є шуваним.

Реалізація

Найпростіша за $O(m \cdot \log n + n^2)$

Дана реалізація є найпростішою і виконується за $O(m \cdot \log n + n^2)$. Сортування ребер займає $O(m \cdot \log n)$ операцій. Належність вершини тому чи іншому дереву зберігається за допомогою масиву tree_id - в ньому для кожної вершини зберігається номер дерева, якому вона належить. Для кожного ребра ми за $O(1)$ визначаємо чи належать його кінці різним деревам. Нарешті, об'єднання двох дерев здійснюється за $O(n)$ простим проходом по масиву tree_id. Враховуючи, що всього операцій з'єднання буде $n-1$, ми і отримуємо асимптотику $O(m \cdot \log n + n^2)$.

int m;
vector<pair<int, pair<int, int>>> g(m); // список ребер у форматі - {вага, {вершина 1, вершина 2}}

int cost = 0;
vector<pair<int, int>> res;

sort(g.begin(), g.end());
vector<int> tree_id(n);

for (int i = 0; i < n; i++) {
    tree_id[i] = i;
}
for (int i = 0; i < m; i++) {
    int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
    if (tree_id[a] != tree_id[b]) {
        cost += l;
        res.push_back(make_pair(a, b));
        int old_id = tree_id[b], new_id = tree_id[a];
        for (int j = 0; j < n; j++) {
            if (tree_id[j] == old_id) {
                tree_id[j] = new_id;
            }
        }
    }
}

Із системою множин, що не перетинаються за $O(m \cdot \log n)$

Розглянемо реалізацію з використанням структури данних "система множин, що не перетинаються" (DSU), яка дозволить досягти асимптотики $O(m \cdot \log n)$.

Так само, як і в простий версії алгоритму Крускала, відсортуємо всі ребра по зростанню ваги. Потім розташуємо кожну вершину в своє дерево (тобто у свою множину) - на це піде в сумі $O(n)$. Перебираємо всі ребра (в порядку сортування) і для кожного ребра за $O(1)$ визначаємо, чи належать його кінці різним деревам за допомогою двох викликів dsu_get за $O(1)$. Об'єднання двох дерев буде звійснюватись викликом dsu_unite - також за $O(1)$. Разом ми отримуємо асимптотику $O(m \cdot \log n + n + m) = O(m \cdot \log n)$.

Тут представленій реалізації використовуватися рандомізована версія DSU.

vector<int> p(n);

int dsu_get(int v) {
    return (v == p[v]) ? v : (p[v] = dsu_get(p[v]));
}

void dsu_unite(int a, int b) {
    a = dsu_get(a);
    b = dsu_get(b);
    if (rand() & 1) {
        swap(a, b);
    }
    if (a != b) {
        p[a] = b;
    }
}

... у функції main(): ...

int m;
vector<pair<int, pair<int, int>>> g; // список ребер у форматі - {вага, {вершина 1, вершина 2}}
... читання графа ...

int cost = 0;
vector<pair<int, int>> res;

sort(g.begin(), g.end());
p.resize(n);
for (int i = 0; i < n; i++) {
    p[i] = i;
}
for (int i = 0; i < m; i++) {
    int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
    if (dsu_get(a) != dsu_get(b)) {
        cost += l;
        res.push_back(g[i].second);
        dsu_unite(a, b);
    }
}

Застосування

TODO: add applications

Задачі

TODO: add problems