Kruskal's Minimum Spanning Tree ใช้ STL ใน C++

คำอธิบาย

อัลกอริทึม Kruskal หา Minimum Spanning Tree (MST) ของกราฟเชื่อมต่อไม่มีทิศทางมีน้ำหนัก ใช้ Disjoint Set Union (DSU) และ เรียง edge ตามน้ำหนัก

ขั้นตอน

1. เรียง edges ตามน้ำหนักน้อยไปมาก
2. สร้าง DSU สำหรับแต่ละ vertex
3. วน edge: ถ้าจุดปลายอยู่คนละ component → union และเพิ่มใน MST
4. หยุดเมื่อมี edge น้อยกว่า V-1

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> iPair;

struct Graph {
    int V, E;
    vector<pair<int, iPair>> edges;
    
    Graph(int V, int E) : V(V), E(E) {}
    
    void addEdge(int u, int v, int w) {
        edges.push_back({w, {u, v}});
    }
    
    int kruskalMST() {
        sort(edges.begin(), edges.end());
        
        // DSU
        vector<int> parent(V), rank(V, 0);
        iota(parent.begin(), parent.end(), 0);
        
        function<int(int)> find = [&](int u) {
            return parent[u] == u ? u : parent[u] = find(parent[u]);
        };
        auto unite = [&](int u, int v) {
            u = find(u); v = find(v);
            if(u == v) return false;
            if(rank[u] < rank[v]) swap(u, v);
            parent[v] = u;
            if(rank[u] == rank[v]) rank[u]++;
            return true;
        };
        
        int mstWeight = 0;
        cout << "Edges in MST:\n";
        for(auto& e : edges) {
            int w = e.first;
            int u = e.second.first;
            int v = e.second.second;
            if(unite(u, v)) {
                cout << u << " - " << v << " (wt: " << w << ")\n";
                mstWeight += w;
            }
        }
        return mstWeight;
    }
};

int main() {
    int V = 9, E = 14;
    Graph g(V, E);
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
    
    cout << "MST Weight: " << g.kruskalMST() << endl;
    return 0;
}

เอาต์พุต

Edges in MST:
6 - 7 (wt: 1)
2 - 8 (wt: 2)
5 - 6 (wt: 2)
0 - 1 (wt: 4)
2 - 5 (wt: 4)
2 - 3 (wt: 7)
0 - 7 (wt: 8)
3 - 4 (wt: 9)
MST Weight: 37