Algoogle

Algorithm for Programming Contest

Kruskal法

基本情報


計算量
用途 最小全域木(森)を求める

E := 辺の数
V := 頂点数

解説


グラフの辺のリストをコストの小さい方から処理していき, 辺の両端の頂点が同じ木に属していなければその辺を使う.
同じ木に属しているかどうかの判定にはUnion-Findを利用する.

コード


(kruskal.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct edge {
    int from, to, cst;
    edge(){}
    edge(int from, int to, int cst) : from(from), to(to), cst(cst) {}
    bool operator<(const edge &e) const { return cst < e.cst; }
};

// Eが連結ならTに最小全域木が入る
int kruskal(vector<edge> &E, vector<edge> &T) {
    sort(E.begin(), E.end());
    T.clear();
    union_find uf(n) ;
    int w = 0;
    for(int i = 0; i < E.size(); i++){
        edge &e = E[i];
        if(uf.same(e.from, e.to)) continue;
        uf.unite(e.from, e.to);
        w += e.cst;
        T.push_back(e);
    }
    return w;
}

問題


Comments