Мінімальне кістякове дерево - алгоритм Пріма

Дано зважений неорієнтований граф $G$ з $n$ вершинами та $m$ ребрами. Ми хочемо знайти кістякове дерево цього графа, яке з'єднує всі вершини й має найменшу вагу (тобто сума ваг ребер мінімальна). Кістякове дерево — це множина ребер така, що з будь-якої вершини можна дістатися до будь-якої іншої рівно одним простим шляхом. Кістякове дерево з найменшою вагою називають мінімальним кістяковим деревом.

На лівому зображенні ви бачите зважений неорієнтований граф, а на правому — відповідне мінімальне кістякове дерево.

Легко бачити, що будь-яке кістякове дерево обов'язково міститиме $n-1$ ребро.

Ця задача доволі природно виникає в багатьох інших задачах. Наприклад, у такій задачі: є $n$ міст, і для кожної пари міст задано вартість будівництва дороги між ними (або ми знаємо, що збудувати дорогу між ними фізично неможливо). Нам треба побудувати дороги так, щоб можна було дістатися з кожного міста до будь-якого іншого, і щоб вартість будівництва всіх доріг була мінімальною.

Коли підходить цей алгоритм?

• Потрібне мінімальне кістякове дерево, а граф щільний (близький до повного) чи заданий матрицею суміжності — наприклад, евклідове MST по точках? (якщо граф розріджений і ребра подані списком → Крускал)
• Зручно нарощувати дерево з однієї вершини, тримаючи для кожної необраної вершини найдешевше ребро до вже обраної частини?

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

Цей алгоритм первісно відкрив чеський математик Войтех Ярнік (Vojtěch Jarník) у 1930 році. Однак цей алгоритм здебільшого відомий як алгоритм Пріма — на честь американського математика Роберта Клея Пріма (Robert Clay Prim), який заново відкрив і опублікував його в 1957 році. Крім того, Едсгер Дейкстра опублікував цей алгоритм у 1959 році.

Опис алгоритму

Тут ми опишемо алгоритм у його найпростішій формі. Мінімальне кістякове дерево будується поступово, додаванням по одному ребру за раз. Спочатку кістякове дерево складається лише з однієї вершини (обраної довільно). Потім обирається ребро мінімальної ваги, що виходить із цієї вершини, і додається до кістякового дерева. Після цього кістякове дерево вже складається з двох вершин. Тепер обираємо й додаємо ребро мінімальної ваги, яке має один кінець у вже обраній вершині (тобто у вершині, що вже належить кістяковому дереву), а інший кінець — у необраній вершині. І так далі, тобто щоразу ми обираємо й додаємо ребро мінімальної ваги, яке з'єднує одну обрану вершину з однією необраною. Процес повторюється, доки кістякове дерево не міститиме всі вершини (або, що те саме, доки ми не матимемо $n - 1$ ребро).

Зрештою побудоване кістякове дерево буде мінімальним. Якщо ж початковий граф не був зв'язним, то кістякового дерева не існує, тож кількість обраних ребер буде меншою за $n - 1$.

Доведення

Нехай граф $G$ зв'язний, тобто відповідь існує. Позначимо через $T$ граф, який отримав алгоритм Пріма, а через $S$ — мінімальне кістякове дерево. Очевидно, що $T$ справді є кістяковим деревом і підграфом $G$. Нам лишається тільки показати, що ваги $S$ і $T$ збігаються.

Розглянемо перший момент в алгоритмі, коли ми додаємо до $T$ ребро, що не належить $S$. Позначимо це ребро через $e$, його кінці — через $a$ і $b$, а множину вже обраних вершин — через $V$ ($a \in V$ і $b \notin V$, або навпаки).

У мінімальному кістяковому дереві $S$ вершини $a$ і $b$ з'єднані деяким шляхом $P$. На цьому шляху ми можемо знайти ребро $f$ таке, що один кінець $f$ лежить у $V$, а інший — ні. Оскільки алгоритм обрав $e$ замість $f$, це означає, що вага $f$ більша або дорівнює вазі $e$.

Додаємо ребро $e$ до мінімального кістякового дерева $S$ і видаляємо ребро $f$. Додавши $e$, ми створили цикл, а оскільки $f$ також належало єдиному циклу, то після його видалення отриманий граф знову не містить циклів. А оскільки ми видалили лише ребро з циклу, отриманий граф усе ще зв'язний.

Отримане кістякове дерево не може мати більшу сумарну вагу, бо вага $e$ не перевищувала ваги $f$, а також не може мати меншу вагу, бо $S$ було мінімальним кістяковим деревом. Це означає, що, замінивши ребро $f$ на $e$, ми отримали інше мінімальне кістякове дерево. А отже, $e$ мусить мати ту саму вагу, що й $f$.

Таким чином, усі ребра, які ми обираємо в алгоритмі Пріма, мають ті самі ваги, що й ребра будь-якого мінімального кістякового дерева, а це означає, що алгоритм Пріма справді породжує мінімальне кістякове дерево.

Реалізація

Складність алгоритму залежить від того, як ми шукаємо наступне мінімальне ребро серед придатних ребер. Існує кілька підходів, що ведуть до різних складностей і різних реалізацій.

Тривіальні реалізації: $O(n m)$ та $O(n^2 + m \log n)$

Якщо ми шукаємо ребро, перебираючи всі можливі ребра, то на пошук ребра мінімальної ваги витрачається $O(m)$ часу. Загальна складність буде $O(n m)$. У найгіршому випадку це $O(n^3)$ — дуже повільно.

Цей алгоритм можна покращити, якщо дивитися лише на одне ребро від кожної вже обраної вершини. Наприклад, ми можемо відсортувати ребра кожної вершини за зростанням їхніх ваг і зберігати вказівник на перше придатне ребро (тобто ребро, що веде до необраної вершини). Тоді після знаходження й вибору мінімального ребра ми оновлюємо вказівники. Це дає складність $O(n^2 + m)$, а на сортування ребер додатково $O(m \log n)$, що в найгіршому випадку дає складність $O(n^2 \log n)$.

Нижче ми розглянемо два дещо різні алгоритми — один для щільних графів, а інший для розріджених, обидва з кращою складністю.

Щільні графи: $O(n^2)$

Підійдемо до цієї задачі під іншим кутом: для кожної ще не обраної вершини зберігатимемо мінімальне ребро до вже обраної вершини.

Тоді на кожному кроці нам треба буде лише переглянути ці ребра мінімальної ваги, що матиме складність $O(n)$.

Після додавання ребра деякі вказівники на мінімальні ребра доведеться перерахувати. Зауважимо, що ваги можуть лише зменшуватися, тобто ребро мінімальної ваги кожної ще не обраної вершини може лишитися тим самим або буде оновлене ребром до щойно обраної вершини. Тому цю фазу теж можна виконати за $O(n)$.

Отже, ми отримали версію алгоритму Пріма зі складністю $O(n^2)$.

Зокрема, ця реалізація дуже зручна для задачі евклідового мінімального кістякового дерева: у нас є $n$ точок на площині, відстань між кожною парою точок — це евклідова відстань між ними, і ми хочемо знайти мінімальне кістякове дерево для цього повного графа. Цю задачу можна розв'язати описаним алгоритмом за час $O(n^2)$ і пам'ять $O(n)$, що неможливо за допомогою алгоритму Крускала.

C++

int n;
vector<vector<int>> adj; // матриця суміжності графа
const int INF = 1000000000; // вага INF означає, що ребра немає

struct Edge {
    int w = INF, to = -1;
};

void prim() {
    int total_weight = 0;
    vector<bool> selected(n, false);
    vector<Edge> min_e(n);
    min_e[0].w = 0;

    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j = 0; j < n; ++j) {
            if (!selected[j] && (v == -1 || min_e[j].w < min_e[v].w))
                v = j;
        }

        if (min_e[v].w == INF) {
            cout << "No MST!" << endl;
            exit(0);
        }

        selected[v] = true;
        total_weight += min_e[v].w;
        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;

        for (int to = 0; to < n; ++to) {
            if (adj[v][to] < min_e[to].w)
                min_e[to] = {adj[v][to], v};
        }
    }

    cout << total_weight << endl;
}

Python

INF = 1000000000  # вага INF означає, що ребра немає
n = 0
adj: list[list[int]] = []  # матриця суміжності графа


def prim() -> int:
    total_weight = 0
    selected = [False] * n
    # для кожної вершини зберігаємо пару (вага, кінець) найдешевшого ребра до
    # вже обраної частини; у щільному варіанті обходимося звичайними масивами
    min_w = [INF] * n
    min_to = [-1] * n
    min_w[0] = 0

    for _ in range(n):
        v = -1
        for j in range(n):
            if not selected[j] and (v == -1 or min_w[j] < min_w[v]):
                v = j

        if min_w[v] == INF:
            print("No MST!")
            raise SystemExit(0)

        selected[v] = True
        total_weight += min_w[v]
        if min_to[v] != -1:
            print(v, min_to[v])

        for to in range(n):
            if adj[v][to] < min_w[to]:
                min_w[to] = adj[v][to]
                min_to[to] = v

    print(total_weight)
    return total_weight

TypeScript

const INF = 1000000000; // вага INF означає, що ребра немає
let n = 0;
let adj: number[][]; // матриця суміжності графа

function prim(): number {
    let totalWeight = 0;
    const selected = new Array<boolean>(n).fill(false);
    // найдешевше ребро до вже обраної частини: вага і кінець зберігаємо в
    // окремих масивах — для щільного графа цього достатньо
    const minW = new Array<number>(n).fill(INF);
    const minTo = new Array<number>(n).fill(-1);
    minW[0] = 0;

    for (let i = 0; i < n; ++i) {
        let v = -1;
        for (let j = 0; j < n; ++j) {
            if (!selected[j] && (v === -1 || minW[j] < minW[v])) v = j;
        }

        if (minW[v] === INF) {
            console.log("No MST!");
            throw new Error("No MST");
        }

        selected[v] = true;
        totalWeight += minW[v];
        if (minTo[v] !== -1) console.log(v, minTo[v]);

        for (let to = 0; to < n; ++to) {
            if (adj[v][to] < minW[to]) {
                minW[to] = adj[v][to];
                minTo[to] = v;
            }
        }
    }

    console.log(totalWeight);
    return totalWeight;
}

Go

import "fmt"

const INF = 1000000000 // вага INF означає, що ребра немає

var n int
var adj [][]int // матриця суміжності графа

func prim() int {
    totalWeight := 0
    selected := make([]bool, n)
    // найдешевше ребро до вже обраної частини: вагу і кінець тримаємо в
    // окремих зрізах — для щільного графа цього достатньо
    minW := make([]int, n)
    minTo := make([]int, n)
    for i := range minW {
        minW[i] = INF
        minTo[i] = -1
    }
    minW[0] = 0

    for i := 0; i < n; i++ {
        v := -1
        for j := 0; j < n; j++ {
            if !selected[j] && (v == -1 || minW[j] < minW[v]) {
                v = j
            }
        }

        if minW[v] == INF {
            fmt.Println("No MST!")
            panic("No MST")
        }

        selected[v] = true
        totalWeight += minW[v]
        if minTo[v] != -1 {
            fmt.Println(v, minTo[v])
        }

        for to := 0; to < n; to++ {
            if adj[v][to] < minW[to] {
                minW[to] = adj[v][to]
                minTo[to] = v
            }
        }
    }

    fmt.Println(totalWeight)
    return totalWeight
}

Матриця суміжності adj[][] розміру $n \times n$ зберігає ваги ребер, причому вона використовує вагу INF, якщо ребра між двома вершинами не існує. Алгоритм використовує два масиви: прапорець selected[], який вказує, які вершини ми вже обрали, і масив min_e[], який для кожної ще не обраної вершини зберігає ребро мінімальної ваги до обраної вершини (він зберігає вагу й кінцеву вершину). Алгоритм виконує $n$ кроків, на кожній ітерації обирається вершина з найменшою вагою ребра, і min_e[] усіх інших вершин оновлюється.

Розріджені графи: $O(m \log n)$

В описаному вище алгоритмі операції пошуку мінімуму й зміни деяких значень можна інтерпретувати як операції над множиною. Ці дві класичні операції підтримуються багатьма структурами даних, наприклад set у C++ (які реалізовано через червоно-чорні дерева).

Основний алгоритм лишається тим самим, але тепер ми можемо знаходити мінімальне ребро за час $O(\log n)$. З іншого боку, перерахунок вказівників тепер займатиме $O(n \log n)$ часу, що гірше, ніж у попередньому алгоритмі.

Але якщо врахувати, що загалом нам потрібно оновлювати лише $O(m)$ разів і виконувати $O(n)$ пошуків мінімального ребра, то загальна складність буде $O(m \log n)$. Для розріджених графів це краще, ніж попередній алгоритм, але для щільних графів це буде повільніше.

C++

const int INF = 1000000000;

struct Edge {
    int w = INF, to = -1;
    bool operator<(Edge const& other) const {
        return make_pair(w, to) < make_pair(other.w, other.to);
    }
};

int n;
vector<vector<Edge>> adj;

void prim() {
    int total_weight = 0;
    vector<Edge> min_e(n);
    min_e[0].w = 0;
    set<Edge> q;
    q.insert({0, 0});
    vector<bool> selected(n, false);
    for (int i = 0; i < n; ++i) {
        if (q.empty()) {
            cout << "No MST!" << endl;
            exit(0);
        }

        int v = q.begin()->to;
        selected[v] = true;
        total_weight += q.begin()->w;
        q.erase(q.begin());

        if (min_e[v].to != -1)
            cout << v << " " << min_e[v].to << endl;

        for (Edge e : adj[v]) {
            if (!selected[e.to] && e.w < min_e[e.to].w) {
                q.erase({min_e[e.to].w, e.to});
                min_e[e.to] = {e.w, v};
                q.insert({e.w, e.to});
            }
        }
    }

    cout << total_weight << endl;
}

Python

import heapq

INF = 1000000000
n = 0
adj: list[list[tuple[int, int]]] = []  # adj[v] = список пар (w, to)


def prim() -> int:
    total_weight = 0
    # min_e[v] = (вага, кінець) найдешевшого ребра від v до вже обраної частини
    min_e_w = [INF] * n
    min_e_to = [-1] * n
    min_e_w[0] = 0
    selected = [False] * n

    # У C++ використано std::set, бо потрібен decrease-key: при оновленні
    # min_e старе ребро видаляється з черги (q.erase). heapq такого не вміє
    # (немає видалення довільного елемента), тому застосовуємо «ліниву» схему:
    # просто кладемо нову пару, а застарілі відсіюємо вже після вилучення.
    q: list[tuple[int, int]] = [(0, 0)]  # пари (вага, вершина)

    for _ in range(n):
        # пропускаємо застарілі записи (вершина вже обрана або вага не свіжа)
        while q and (selected[q[0][1]] or q[0][0] != min_e_w[q[0][1]]):
            heapq.heappop(q)
        if not q:
            print("No MST!")
            raise SystemExit(0)

        w, v = heapq.heappop(q)
        selected[v] = True
        total_weight += w

        if min_e_to[v] != -1:
            print(v, min_e_to[v])

        for ew, to in adj[v]:
            if not selected[to] and ew < min_e_w[to]:
                min_e_w[to] = ew
                min_e_to[to] = v
                heapq.heappush(q, (ew, to))  # стару пару лишаємо «застарілою»

    print(total_weight)
    return total_weight

TypeScript

const INF = 1000000000;
let n = 0;
let adj: Array<Array<[number, number]>>; // adj[v] = масив пар [w, to]

// std::set із C++ дозволяє decrease-key (видалити старе ребро з черги).
// У стандартній бібліотеці JS/TS купи немає взагалі, тому реалізуємо бінарну
// min-купу пар [вага, вершина] і застосовуємо «ліниву» схему замість
// видалення довільного елемента: застарілі пари відсіюємо при вилученні.
class MinHeap {
    private a: Array<[number, number]> = [];
    get size(): number {
        return this.a.length;
    }
    push(item: [number, number]): void {
        const a = this.a;
        a.push(item);
        let i = a.length - 1;
        while (i > 0) {
            const parent = (i - 1) >> 1;
            if (a[parent][0] <= a[i][0]) break;
            [a[parent], a[i]] = [a[i], a[parent]];
            i = parent;
        }
    }
    top(): [number, number] {
        return this.a[0];
    }
    pop(): [number, number] {
        const a = this.a;
        const top = a[0];
        const last = a.pop()!;
        if (a.length > 0) {
            a[0] = last;
            let i = 0;
            const m = a.length;
            for (;;) {
                const l = 2 * i + 1;
                const r = 2 * i + 2;
                let smallest = i;
                if (l < m && a[l][0] < a[smallest][0]) smallest = l;
                if (r < m && a[r][0] < a[smallest][0]) smallest = r;
                if (smallest === i) break;
                [a[smallest], a[i]] = [a[i], a[smallest]];
                i = smallest;
            }
        }
        return top;
    }
}

function prim(): number {
    let totalWeight = 0;
    // найдешевше ребро від кожної вершини до вже обраної частини
    const minEW = new Array<number>(n).fill(INF);
    const minETo = new Array<number>(n).fill(-1);
    minEW[0] = 0;
    const selected = new Array<boolean>(n).fill(false);

    const q = new MinHeap();
    q.push([0, 0]); // пари [вага, вершина]

    for (let i = 0; i < n; ++i) {
        // відкидаємо застарілі пари (вершина вже обрана або вага несвіжа)
        while (q.size > 0 && (selected[q.top()[1]] || q.top()[0] !== minEW[q.top()[1]])) {
            q.pop();
        }
        if (q.size === 0) {
            console.log("No MST!");
            throw new Error("No MST");
        }

        const [w, v] = q.pop();
        selected[v] = true;
        totalWeight += w;

        if (minETo[v] !== -1) console.log(v, minETo[v]);

        for (const [ew, to] of adj[v]) {
            if (!selected[to] && ew < minEW[to]) {
                minEW[to] = ew;
                minETo[to] = v;
                q.push([ew, to]); // стару пару лишаємо «застарілою»
            }
        }
    }

    console.log(totalWeight);
    return totalWeight;
}

Go

import (
    "container/heap"
    "fmt"
)

const INF = 1000000000

var n int
var adj [][][2]int // adj[v] = список пар {w, to}

// C++ std::set дає decrease-key (видалення старого ребра з черги). У Go такого
// впорядкованого контейнера немає; беремо container/heap і застосовуємо
// «ліниву» схему: застарілі пари не видаляємо, а відсіюємо при вилученні.
// Елемент — пара {вага, вершина}, Less упорядковує за вагою.
type pq [][2]int

func (h pq) Len() int            { return len(h) }
func (h pq) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h pq) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *pq) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *pq) Pop() interface{} {
    old := *h
    m := len(old)
    item := old[m-1]
    *h = old[:m-1]
    return item
}

func prim() int {
    totalWeight := 0
    // найдешевше ребро від кожної вершини до вже обраної частини
    minEW := make([]int, n)
    minETo := make([]int, n)
    for i := range minEW {
        minEW[i] = INF
        minETo[i] = -1
    }
    minEW[0] = 0
    selected := make([]bool, n)

    q := &pq{{0, 0}} // пари {вага, вершина}
    heap.Init(q)

    for i := 0; i < n; i++ {
        // відкидаємо застарілі пари (вершина вже обрана або вага несвіжа)
        for q.Len() > 0 && (selected[(*q)[0][1]] || (*q)[0][0] != minEW[(*q)[0][1]]) {
            heap.Pop(q)
        }
        if q.Len() == 0 {
            fmt.Println("No MST!")
            panic("No MST")
        }

        top := heap.Pop(q).([2]int)
        w, v := top[0], top[1]
        selected[v] = true
        totalWeight += w

        if minETo[v] != -1 {
            fmt.Println(v, minETo[v])
        }

        for _, e := range adj[v] {
            ew, to := e[0], e[1]
            if !selected[to] && ew < minEW[to] {
                minEW[to] = ew
                minETo[to] = v
                heap.Push(q, [2]int{ew, to}) // стару пару лишаємо «застарілою»
            }
        }
    }

    fmt.Println(totalWeight)
    return totalWeight
}

Тут граф подано через список суміжності adj[], де adj[v] містить усі ребра (у вигляді пар «вага й ціль») для вершини v. min_e[v] зберігатиме вагу найменшого ребра від вершини v до вже обраної вершини (знову ж таки у вигляді пари «вага й ціль»). Крім того, чергу q заповнено всіма ще не обраними вершинами в порядку зростання ваг min_e. Алгоритм виконує n кроків, на кожному з яких обирає вершину v з найменшою вагою min_e (вилучаючи її з початку черги), а потім переглядає всі ребра з цієї вершини й оновлює значення в min_e (під час оновлення нам також потрібно видалити старе ребро з черги q і вставити нове ребро).

Відеоматеріали