Minimum Spanning Tree (MST)

Spanning Tree คือ subgraph ที่เชื่อมทุก vertex โดยไม่มี cycle และมี edges = V - 1

Minimum Spanning Tree คือ spanning tree ที่มีผลรวมน้ำหนัก edges น้อยที่สุด

Kruskal’s Algorithm

ใช้ Greedy approach: เลือก edge ที่น้ำหนักน้อยที่สุดที่ไม่ทำให้เกิด cycle

Algorithm

1. เรียง edges ตามน้ำหนักจากน้อยไปมาก
2. ไล่เลือก edge ทีละอัน
3. ถ้า edge ไม่ทำให้เกิด cycle ให้เพิ่มเข้า MST
4. ทำจนครบ V-1 edges

Implementation (ใช้ DSU)

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

class DSU {
public:
    vector<int> parent, rank_;
    
    DSU(int n) {
        parent.resize(n + 1);
        rank_.resize(n + 1, 0);
        for (int i = 0; i <= n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        // Union by rank
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        
        return true;
    }
};

pair<long long, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    
    DSU dsu(n);
    long long totalWeight = 0;
    vector<Edge> mst;
    
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            totalWeight += e.w;
            mst.push_back(e);
            
            if (mst.size() == n - 1) break;
        }
    }
    
    return {totalWeight, mst};
}

Complexity

• Time: $O(E \log E)$ (sorting edges)
• Space: $O(V)$ for DSU

Prim’s Algorithm

ใช้ Greedy approach: เริ่มจาก vertex หนึ่ง แล้วขยาย MST โดยเลือก edge ที่น้ำหนักน้อยที่สุด

Algorithm

1. เริ่มจาก vertex ใดก็ได้
2. ใช้ priority queue เก็บ edges ที่เชื่อมกับ MST
3. เลือก edge ที่น้ำหนักน้อยที่สุดไปยัง vertex ที่ยังไม่อยู่ใน MST
4. ทำจนครบ V vertices

Implementation

pair<long long, vector<pair<int, int>>> prim(int start, vector<vector<pair<int, int>>>& adj) {
    int n = adj.size();
    vector<bool> inMST(n, false);
    vector<int> key(n, INF);    // minimum edge weight to reach vertex
    vector<int> parent(n, -1);
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    key[start] = 0;
    pq.push({0, start});
    
    long long totalWeight = 0;
    
    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        
        if (inMST[u]) continue;
        
        inMST[u] = true;
        totalWeight += w;
        
        for (auto [v, edgeWeight] : adj[u]) {
            if (!inMST[v] && edgeWeight < key[v]) {
                key[v] = edgeWeight;
                parent[v] = u;
                pq.push({key[v], v});
            }
        }
    }
    
    // สร้าง MST edges
    vector<pair<int, int>> mstEdges;
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            mstEdges.push_back({parent[i], i});
        }
    }
    
    return {totalWeight, mstEdges};
}

Complexity

• Time: $O((V + E) \log V)$ with priority queue
• Space: $O(V)$

Kruskal vs Prim

เงื่อนไข	ใช้
Sparse Graph (E ≈ V)	Kruskal
Dense Graph (E ≈ V²)	Prim
ต้องการ edges ใน MST	Kruskal (ง่ายกว่า)
Graph เป็น adjacency list	Prim

MST Properties

1. Uniqueness

MST จะ unique ถ้า edge weights ทั้งหมดแตกต่างกัน

2. Cut Property

สำหรับ cut ใดๆ edge ที่มีน้ำหนักน้อยที่สุดข้าม cut จะอยู่ใน MST

3. Cycle Property

สำหรับ cycle ใดๆ edge ที่มีน้ำหนักมากที่สุดใน cycle จะไม่อยู่ใน MST

Second Best MST

หา MST ที่มีน้ำหนักรองลงมา

// วิธี Brute Force: ลอง remove แต่ละ edge ใน MST
long long secondBestMST(int n, vector<Edge>& edges) {
    auto [mstWeight, mstEdges] = kruskal(n, edges);
    
    long long secondBest = LLONG_MAX;
    
    for (int i = 0; i < mstEdges.size(); i++) {
        // สร้าง edges โดยไม่รวม edge ที่ i
        vector<Edge> newEdges;
        for (auto& e : edges) {
            if (!(e.u == mstEdges[i].u && e.v == mstEdges[i].v && 
                  e.w == mstEdges[i].w)) {
                newEdges.push_back(e);
            }
        }
        
        auto [newWeight, newMST] = kruskal(n, newEdges);
        if (newMST.size() == n - 1) { // ยังเป็น spanning tree
            secondBest = min(secondBest, newWeight);
        }
    }
    
    return secondBest;
}

Maximum Spanning Tree

เปลี่ยน comparison ให้เรียงจากมากไปน้อย

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w > other.w; // มากไปน้อย
    }
};

ตัวอย่างโจทย์

โจทย์ 1: หา MST Weight

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    
    auto [totalWeight, mst] = kruskal(n, edges);
    
    if (mst.size() != n - 1) {
        cout << "IMPOSSIBLE" << endl; // Graph ไม่ connected
    } else {
        cout << totalWeight << endl;
    }
}

โจทย์ 2: เชื่อม Cities ด้วย Cost ต่ำสุด

// ให้ n cities และ cost ในการเชื่อมแต่ละคู่
// หา minimum total cost

int main() {
    int n;
    cin >> n;
    
    vector<Edge> edges;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int cost;
            cin >> cost;
            edges.push_back({i, j, cost});
        }
    }
    
    auto [totalCost, mst] = kruskal(n, edges);
    cout << totalCost << endl;
}

โจทย์ 3: MST บน Grid

// n × m grid แต่ละ cell มี height
// cost ในการเดินระหว่าง cells = |height difference|
// หา minimum cost ในการเชื่อมทุก cells

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    auto idx = [&](int i, int j) { return i * m + j; };
    
    vector<Edge> edges;
    int dx[] = {0, 1};
    int dy[] = {1, 0};
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int d = 0; d < 2; d++) {
                int ni = i + dx[d], nj = j + dy[d];
                if (ni < n && nj < m) {
                    int cost = abs(grid[i][j] - grid[ni][nj]);
                    edges.push_back({idx(i, j), idx(ni, nj), cost});
                }
            }
        }
    }
    
    auto [totalCost, mst] = kruskal(n * m, edges);
    cout << totalCost << endl;
}

สรุป

Algorithm	Best For	Complexity
Kruskal	Sparse graph, Edge list	$O(E \log E)$
Prim	Dense graph, Adj list	$O((V+E) \log V)$

💡 Tip: Kruskal + DSU เป็นการ implement ที่ง่ายและใช้บ่อยที่สุดในการแข่งขัน