Хамгийн бага тэлэх мод - Крускал огтлолцолгүй олонлогийн нэгдэлтэй¶

MST бодлого ба Крускалын алгоритмын тайлбарыг эхлээд Крускалын алгоритмын үндсэн өгүүллээс үзнэ үү.

Энэ өгүүлэлд бид Крускалын алгоритмыг хэрэгжүүлэхэд "Огтлолцолгүй олонлогийн нэгдэл" өгөгдлийн бүтцийг авч үзэх ба энэ нь алгоритмд $O(M \log N)$ time complexity-д хүрэх боломж олгоно.

Тайлбар¶

Крускалын алгоритмын энгийн хувилбарын нэгэн адил бид графын бүх ирмэгийг жингийн буурахгүй дарааллаар эрэмбэлнэ. Дараа нь make_set функцийн дуудлагаар орой бүрийг өөрийн модонд (өөрөөр хэлбэл өөрийн олонлогт) байрлуулна — энэ нь нийтдээ $O(N)$ авна. Бид бүх ирмэгийг (эрэмбэлэгдсэн дарааллаар) тойрч, ирмэг бүрийн хувьд үзүүрүүд нь өөр өөр модонд харьяалагдах эсэхийг тодорхойлно (тус бүр $O(1)$-д хийгдэх хоёр find_set дуудлагаар). Эцэст нь бид хоёр модыг (олонлогийг) нэгтгэх хэрэгтэй, үүний тулд DSU-ийн union_sets функц дуудагдана — мөн $O(1)$-д. Ингэснээр бид нийт $O(M \log N + N + M)$ = $O(M \log N)$ time complexity авна.

Implementation¶

Here is an implementation of Kruskal's algorithm with Union by Rank.

vector<int> parent, rank;

void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

int n;
vector<Edge> edges;

int cost = 0;
vector<Edge> result;
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++)
    make_set(i);

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

for (Edge e : edges) {
    if (find_set(e.u) != find_set(e.v)) {
        cost += e.weight;
        result.push_back(e);
        union_sets(e.u, e.v);
    }
}

Анхаарна уу: MST яг $N-1$ ирмэг агуулах тул бид тэр тооны ирмэг олмогцоо давталтыг зогсоож болно.

Дасгал бодлогууд¶

Энэ сэдвийн дасгал бодлогуудын жагсаалтыг Крускалын алгоритмын үндсэн өгүүллээс үзнэ үү.