fc2ブログ



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

2006.04.26 22:53  グラフ 最小全域木

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) を取得し、以下の処理を行います。
もし uv が同じ集合に属していないならば
つまり、dset.findSet( u ) ≠ dset.findSet( v ) ならば、
    u, vT に追加し、
    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 );
        }
    }
}
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ