Kruskal's Algorithm クラスカルのアルゴリズム

Kruskal's Algorithm は、グラフ G(V, E) の MST を求めるためのアルゴリズムです。これも Greedy Algorithm で、各計算ステップで、最も適したエッジを選び、MST を求めます。このアルゴリズムを実装するために必要なデータ構造が Disjoint Sets です。Kruskal's Algorithm は以下のように実装します。

	グラフ G(V, E) のノード全体の集合を V、 エッジ全体の集合を E、 MST に属するノードの集合を T とし、 Disjoint Sets のデータ構造 dset を用意します。
1.	V の全ての要素 v を互いに素な集合とします つまり、全ての v に対して dset.makeSet( v ) を行います。
2.	E を、重みが小さい順に整列します。
3.	E から順番にエッジ (u, v) を取得し、以下の処理を行います。
	もし　u と v が同じ集合に属していないならば つまり、dset.findSet( u ) ≠ dset.findSet( v ) ならば、     u, v を T に追加し、     u, v を合併する。すなわち dset.union( u, v ) を行います。

class edge{
    public:
    int source, target;
    double cost;
    edge(){}
    edge( int source, int target, double cost ):
    source(source), target(target), cost(cost){}
    
    bool operator < ( const edge &e ) const{
        return cost < e.cost;
    }
};

int N;
vector<edge> edges;

void kruskal( vector<edge> &mst ){
    
    sort( edges.begin(), edges.end() );
    
    DisjointSet dset = DisjointSet( N );
    
    for ( int i = 0; i < N; i++ ) dset.makeSet( i );
    
    int source, target;
    for ( int i = 0; i < edges.size(); i++ ){
        edge e = edges[i];
        if ( dset.findSet( e.source ) != dset.findSet( e.target ) ){
            mst.push_back( e );
            dset.union( e.source, e.target );
        }
    }
}