Алгоритм Краскала: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 5 промежуточных версий этого же участника)
Строка 1: Строка 1:
Сначала сортируем список рёбер по неубыванию весов.
Затем проходим по отсортированному списку рёбер и добавляем очередное ребро в остовное дерево, если его концы принадлежат разным компонентам связности. Для проверки этого факта используем [[Система непересекающихся множеств|систему непересекающихся множеств]].
// Система непересекающихся множеств для быстрого определения, лежат ли концы ребра в разных компонентах связности
struct DSU {
    vector<int> parent;
   
    DSU(int n) {
        for (int v = 0; v < n; v++)
            parent.push_back(v);
    }
   
    int findRoot(int v) {
        return parent[v] == v ? v : parent[v] = findRoot(parent[v]);
    }
   
    bool connected(int v1, int v2) {
        return findRoot(v1) == findRoot(v2);
    }
   
    void merge(int v1, int v2) {
        int r1 = findRoot(v1), r2 = findRoot(v2);
        if (r1 == r2)
            return;
        if (rand() % 2)
            parent[r1] = r2;
        else
            parent[r2] = r1;
    }
};
// Структура для хранения взвешенного ребра
// Рёбра сравниваются по весу, список рёбер будет сортироваться по неубыванию весов
struct Edge {
    int a, b, weight;
   
    bool operator < (const Edge &that) const {
        return weight < that.weight;
    }
};
// Считывание списка рёбер графа
// (вершины во вводе нумеруются с 1, во внутреннем представлении — с 0)
int vertexCount, edgeCount;
cin >> vertexCount >> edgeCount;
vector<Edge> edges(edgeCount);
for (auto &[a, b, weight] : edges) {
    cin >> a >> b >> weight;
    a--;
    b--;
}
// Алгоритм Краскала
// (в данном примере определяется вес минимального остовного дерева — mstWeight)
int mstWeight = 0;
sort(edges.begin(), edges.end());
DSU dsu(vertexCount);
for (auto &[a, b, weight] : edges) {
    if (!dsu.connected(a, b)) {
        dsu.merge(a, b);
        mstWeight += weight;
    }
}
Сложность алгоритма Краскала:
* 1 раз выполняется сортировка списка рёбер за время O(ElogE);
* E раз выполняется запрос к системе непересекающихся множеств за O(1).
Итого сложность O(ElogE) = O(ElogV).
Для разреженных графов алгоритмы Прима и Краскала одинаково эффективны. Для плотных графов соответствующий вариант алгоритма Прима эффективнее, чем алгоритм Краскала.
== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/mst_kruskal_with_dsu e-maxx.ru &mdash; Алгоритм Крускала с системой непересекающихся множеств]
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0 neerc.ifmo.ru/wiki &mdash; Алгоритм Краскала]
:* [http://e-maxx.ru/algo/mst_kruskal_with_dsu e-maxx.ru Алгоритм Крускала с системой непересекающихся множеств]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 8]
:* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0 neerc.ifmo.ru/wiki Алгоритм Краскала]
* [http://github.com/ADJA/algos/blob/master/Graphs/MSTKruskal.cpp Algos &mdash; Minimum spanning tree using Kruskal algorithm with DSU]
:* [https://brestprog.by/topics/mst/ brestprog.by — Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала]
:* [https://algorithmica.org/ru/mst algorithmica.org — Минимальные остовы]
:* [https://usaco.guide/gold/mst usaco.guide — MST]
:* [https://algs4.cs.princeton.edu/lectures/keynote/43MinimumSpanningTrees.pdf algs4.cs.princeton.edu/lectures — 4.3 Minimum Spanning Trees]
Демонстрация:
:* [https://visualgo.net/en/mst VisuAlgo — Minimum Spanning Tree]
Код:
:* [https://github.com/ADJA/algos/blob/master/Graphs/MSTKruskal.cpp algos/Graphs/MSTKruskal.cpp]
:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/KruskalMST.java algs4/KruskalMST.java]
 


[[Category:Минимальное остовное дерево]]
[[Category:Минимальное остовное дерево]]

Текущая версия от 04:57, 13 января 2021

Сначала сортируем список рёбер по неубыванию весов.

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

// Система непересекающихся множеств для быстрого определения, лежат ли концы ребра в разных компонентах связности

struct DSU {
    vector<int> parent;
    
    DSU(int n) {
        for (int v = 0; v < n; v++)
            parent.push_back(v);
    }
    
    int findRoot(int v) {
        return parent[v] == v ? v : parent[v] = findRoot(parent[v]);
    }
    
    bool connected(int v1, int v2) {
        return findRoot(v1) == findRoot(v2);
    }
    
    void merge(int v1, int v2) {
        int r1 = findRoot(v1), r2 = findRoot(v2);
        if (r1 == r2)
            return;
        if (rand() % 2)
            parent[r1] = r2;
        else
            parent[r2] = r1;
    }
};
// Структура для хранения взвешенного ребра
// Рёбра сравниваются по весу, список рёбер будет сортироваться по неубыванию весов

struct Edge {
    int a, b, weight;
    
    bool operator < (const Edge &that) const {
        return weight < that.weight;
    }
};
// Считывание списка рёбер графа
// (вершины во вводе нумеруются с 1, во внутреннем представлении — с 0)

int vertexCount, edgeCount;
cin >> vertexCount >> edgeCount;

vector<Edge> edges(edgeCount);
for (auto &[a, b, weight] : edges) {
    cin >> a >> b >> weight;
    a--;
    b--;
}
// Алгоритм Краскала
// (в данном примере определяется вес минимального остовного дерева — mstWeight)

int mstWeight = 0;

sort(edges.begin(), edges.end());

DSU dsu(vertexCount);
for (auto &[a, b, weight] : edges) {
    if (!dsu.connected(a, b)) {
        dsu.merge(a, b);
        mstWeight += weight;
    }
}

Сложность алгоритма Краскала:

  • 1 раз выполняется сортировка списка рёбер за время O(ElogE);
  • E раз выполняется запрос к системе непересекающихся множеств за O(1).

Итого сложность O(ElogE) = O(ElogV).

Для разреженных графов алгоритмы Прима и Краскала одинаково эффективны. Для плотных графов соответствующий вариант алгоритма Прима эффективнее, чем алгоритм Краскала.

Ссылки

Теория:

Демонстрация:

Код: