Cây khung nhỏ nhất: hiểu và chọn Kruskal hay Prim

Nối toàn mạng khác tìm một đường ngắn nhất

Giả sử cần kéo cáp nối các máy trong một mạng. Mỗi cạnh là một tuyến có thể lắp, trọng số là chi phí lắp tuyến đó. Mục tiêu là mọi máy có thể liên lạc với nhau và tổng tiền cho các tuyến đã chọn nhỏ nhất. Không cần giữ mọi cạnh của mạng ban đầu.

Nếu tập cạnh chọn có một chu trình, bỏ một cạnh trong vòng vẫn giữ khả năng nối giữa các đỉnh của vòng. Với bài cây khung, ta cần cấu trúc không có chu trình và nối đủ, nên có đúng n−1 cạnh khi n dương. Tổng trọng số của cấu trúc này mới là thứ cần tối ưu.

MST không bảo đảm đường từ một nguồn tới mọi đỉnh ngắn nhất. Trong hình, đường trong MST từ 1 tới 3 đi qua 2, có giá 3; mục tiêu vẫn là tổng cả mạng bằng 4. Với một đồ thị khác, đường trong MST có thể dài hơn đường trực tiếp bị bỏ. Nếu đề hỏi chi phí hành trình từ s tới t, trước hết hãy nghĩ tới bài đường đi, không tự động dùng cây khung.

Kruskal: thử cạnh rẻ trước

Sắp xếp tất cả cạnh theo trọng số tăng dần. Khởi tạo mỗi đỉnh là một nhóm DSU. Với cạnh u–v, nếu hai đầu chưa chung nhóm thì lấy cạnh và gộp nhóm; nếu đã chung nhóm thì bỏ vì thêm cạnh đó sẽ tạo một vòng trong rừng đang có.

Chỉ kiểm “đã thăm hai đầu chưa” là không đủ. Hai đỉnh đều có thể đã được nối ở hai nhóm khác nhau, và cạnh giữa chúng vẫn cần được lấy. DSU trả lời đúng câu hỏi về thành phần liên thông hiện tại, khác một cờ visited riêng lẻ.

Hai cạnh đồng giá có thể đổi thứ tự mà vẫn cho tổng tối ưu. Nếu đề yêu cầu một cây cụ thể theo quy tắc phụ, phải xử lý quy tắc đó riêng; chỉ hỏi tổng trọng số thì không được coi một đáp án cạnh khác mẫu là sai.

Prim: mở rộng từ một tập đã nối

Bắt đầu từ một đỉnh bất kỳ, coi tập S chứa nó. Trong các cạnh có một đầu thuộc S và đầu kia chưa thuộc S, lấy cạnh rẻ nhất để đưa thêm một đỉnh vào. Heap lưu các cạnh biên; bản ghi dẫn tới đỉnh đã có trong S bị bỏ khi lấy ra.

Với hình, bắt đầu từ 0: cạnh biên rẻ nhất là 0–1 giá 1. Sau khi thêm 1, cạnh 1–2 giá 2 thắng cạnh 0–2 giá 4 và 1–3 giá 5. Thêm 2 rồi chọn 2–3 giá 1. Tổng vẫn là 1+2+1=4, dù chuỗi trọng số được lấy không tăng dần như Kruskal.

Đừng thay khóa Prim bằng d[u]+w như Dijkstra. Prim so giá của cạnh nối thêm một đỉnh vào cây; Dijkstra so tổng giá từ nguồn tới đỉnh. Cả hai dùng min-heap, nhưng ý nghĩa khóa và kết quả cần tìm khác nhau.

Vì sao cạnh rẻ qua lát cắt là an toàn?

Một lát cắt chia tập đỉnh thành hai phần. Giả sử rừng cạnh đã chọn chưa đi qua lát cắt đó. Xét cạnh rẻ nhất e nối hai phía. Nếu một MST đang xét chưa có e, thêm e tạo vòng; trên vòng phải có một cạnh f khác cũng đi qua lát cắt. Vì e không đắt hơn f, đổi f lấy e không làm tổng tăng.

Lập luận đổi cạnh này cho biết có ít nhất một MST chứa lựa chọn an toàn. Prim áp dụng trực tiếp lát cắt S và phần còn lại. Kruskal áp dụng với một thành phần DSU ở thời điểm nhận cạnh. Không cần giả định trọng số dương để lập luận đúng; cạnh âm vẫn có thể tham gia MST bình thường.

Tính chất nói về cạnh nhẹ nhất qua lát cắt, không phải bất kỳ cạnh rẻ nào mà ta thích. Quy tắc “lấy n−1 cạnh rẻ nhất” bỏ qua điều kiện chu trình và có thể bỏ sót một đỉnh. DSU hoặc tập S chính là phần giữ lựa chọn tham lam trong phạm vi có chứng minh.

Code C++ và Python cho cả hai cách

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using Edge=tuple<int,int,long long>;
class DSU{
    vector<int> p,sz;
public:
    int groups;
    explicit DSU(int n):p(n),sz(n,1),groups(n){iota(p.begin(),p.end(),0);}
    int find(int x){while(x!=p[x]){p[x]=p[p[x]];x=p[x];}return x;}
    bool unite(int a,int b){
        a=find(a);b=find(b);if(a==b)return false;
        if(sz[a]<sz[b])swap(a,b);
        p[b]=a;sz[a]+=sz[b];--groups;return true;
    }
};
pair<long long,int> kruskal(int n,vector<Edge> edges){
    sort(edges.begin(),edges.end(),[](auto a,auto b){return get<2>(a)<get<2>(b);});
    DSU d(n);long long total=0;
    for(auto [u,v,w]:edges)if(d.unite(u,v))total+=w;
    return {total,d.groups};
}
pair<long long,int> prim(int n,const vector<Edge>& edges){
    vector<vector<pair<int,long long>>> g(n);
    for(auto [u,v,w]:edges){g[u].push_back({v,w});g[v].push_back({u,w});}
    vector<bool> used(n,false);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q;
    long long total=0;int groups=0;
    for(int root=0;root<n;++root)if(!used[root]){
        ++groups;q.push({0,root});
        while(!q.empty()){
            auto [w,u]=q.top();q.pop();
            if(used[u])continue;
            used[u]=true;total+=w;
            for(auto [v,c]:g[u])if(!used[v])q.push({c,v});
        }
    }
    return {total,groups};
}
int main(){
    int n=4,m;vector<Edge> e={{0,1,1},{1,2,2},{0,2,4},{2,3,1},{1,3,5}};
    if(cin>>n>>m){e.resize(m);for(auto& [u,v,w]:e)cin>>u>>v>>w;}
    for(auto [w,c]:{kruskal(n,e),prim(n,e)})cout<<w<<' '<<c<<'\n';
}

import heapq
import sys

def kruskal(n,edges):
    p=list(range(n));size=[1]*n
    def find(x):
        while p[x]!=x:
            p[x]=p[p[x]]
            x=p[x]
        return x
    total=0;groups=n
    for u,v,w in sorted(edges,key=lambda e:e[2]):
        a,b=find(u),find(v)
        if a==b:
            continue
        if size[a]<size[b]:
            a,b=b,a
        p[b]=a;size[a]+=size[b]
        groups-=1;total+=w
    return total,groups

def prim(n,edges):
    g=[[] for _ in range(n)]
    for u,v,w in edges:
        g[u].append((v,w));g[v].append((u,w))
    used=[False]*n
    total=groups=0
    for root in range(n):
        if used[root]:
            continue
        groups+=1
        q=[(0,root)]
        while q:
            w,u=heapq.heappop(q)
            if used[u]:
                continue
            used[u]=True;total+=w
            for v,c in g[u]:
                if not used[v]:
                    heapq.heappush(q,(c,v))
    return total,groups

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    n=4;edges=[(0,1,1),(1,2,2),(0,2,4),(2,3,1),(1,3,5)]
    if a:
        n,m=a[:2]
        edges=[tuple(a[2+3*i:5+3*i]) for i in range(m)]
    print(*kruskal(n,edges))
    print(*prim(n,edges))

Không nhập thì hai dòng đều là 4 1: tổng trọng số 4 và một thành phần. Dữ liệu riêng có n, m rồi m bộ u v w cho cạnh vô hướng. Code chấp nhận cạnh song song, cạnh tự nối và trọng số âm. Các đầu cạnh phải hợp lệ; tổng trọng số và các giá trị C++ cần nằm trong miền long long.

Hai hàm trả tổng rừng khung nhỏ nhất và số thành phần, nên còn xử lý được đồ thị rời rạc. Kruskal tự để lại các nhóm không nối nhau. Prim chạy lại từ mỗi đỉnh chưa dùng, thêm khóa 0 cho gốc của thành phần mới. Nếu đề yêu cầu nối toàn bộ mạng, n dương và số thành phần khác 1 thì phải báo không thể, thay vì in tổng rừng như đáp án MST.

Với n=0, code trả tổng 0 và 0 thành phần như quy ước dữ liệu rỗng. Đây không phải khẳng định một đồ thị rỗng có cây khung theo mọi định nghĩa. Khi n=1 không cạnh, tổng 0 và một thành phần là trường hợp đơn giản cần kiểm.

Khi nào chọn Kruskal, khi nào chọn Prim?

Kruskal cần O(m log(m+1)) cho sắp xếp, cộng khởi tạo O(n) và các thao tác DSU gần tuyến tính theo số cạnh. Prim lười bằng heap có cận O(n+m log(m+1)) thời gian và O(n+m) bộ nhớ gồm đồ thị với các bản ghi biên. Với đồ thị đơn thường viết phần heap theo log n. Prim quét mảng O(n²) lại có ích trên đồ thị dày hoặc khi tính trọng số cạnh theo công thức mà không muốn liệt kê hết chúng.

Không nên quyết định chỉ bằng câu “Prim luôn nhanh hơn” hoặc “Kruskal luôn dễ hơn”. Cách dữ liệu được cung cấp, mật độ cạnh, giới hạn bộ nhớ và yêu cầu mở rộng mới quyết định lựa chọn. Với người mới, Kruskal là cách tốt để nối kiến thức sắp xếp và DSU đã học.

Kiểm thử bằng vét cạn các tập cạnh nhỏ

Để kiểm tra kỹ trên đồ thị nhỏ (n ≤ 6, m ≤ 10), bạn có thể duyệt mọi tập con gồm n - 1 cạnh, giữ lại những tập làm đồ thị liên thông rồi lấy tổng trọng số nhỏ nhất để so sánh với cả Kruskal và Prim.

Các ca gồm n=0, n=1, đồ thị không cạnh, cạnh âm, cạnh song song và vòng tự nối. Hãy tự thử tam giác ba cạnh giá 1: có nhiều MST tổng 2. Tiếp tục thử hai cặp đỉnh tách biệt: tổng rừng có thể tính được, nhưng không thể gọi đó là cây nối toàn bộ bốn đỉnh.

Luyện ngay trên Big-O Coding

Bài Kruskal luyện trực tiếp khung sắp xếp và DSU. Phân loại cạnh trong các MST là bài nâng cao: các cạnh đồng trọng số cần được xét cẩn thận, và kiến thức cầu sẽ giúp phân biệt cạnh bắt buộc với cạnh có thể thay thế.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Kruskal with DSU
• CP-Algorithms: Prim
• CP-Algorithms: Kruskal