← Static tasks

E040. Минимальное остовное дерево. Алгоритм Крускала с системой непересекающихся множеств

emaxx algorithm

#algorithm#dsu#emaxx#graph#tree

Task

Источник: e-maxx.ru/algo, страница PDF 124.

Постановку задачи и описание алгоритма Крускала см. здесь. Здесь будет рассмотрена реализация с использованием структуры данных "система непересекающихся множеств" (DSU), которая позволит достигнуть асимптотики O (M log N).

Описание

Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. своё множество) с помощью вызова функции DSU MakeSet - на это уйдёт в сумме O (N). Перебираем все рёбра (в порядке сортировки) и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев будет осуществляться вызовом Union - также за O (1). Итого мы получаем асимптотику O (M log N + N + M) = O (M 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);

} }

C# solution

auto-draft, review before submit
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    List<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);
            }
    }
}

C++ solution

matched/original
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);
        }
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    ArrayList<Integer> 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);
            }
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.