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 );
        }
    }
}

Prim's Algorithm プリムのアルゴリズム

Prim's Algorithm は、グラフ G(V, E) の最小全域木 (MST) を求めるための、最も一般的なアルゴリズムです。基本的な考え方は以下のようになります。

	グラフ G(V, E) のノード全体の集合を V、 MST に属するノードの集合を T とします。
1.	G(V, E) から任意のノード r を選び、それを MST のルートとして、T に追加します。
2.	以下のようなエッジ (u, v) を選択します。
	- u は T に属し、v は V - T に属する。 - エッジ (u, v) は、T に属するノードとV - T に属するノードをつなぐエッジの中で、重みが最小のものである。
	v を T に追加します。
	この処理を、T = V になるまで繰り返します。

このアルゴリズムを実装するポイントは、各選択ステップで "どのように最小の重みをもつエッジを記録するか" です。Prim's Algorithm は以下のように実装します。

	グラフ G(V, E) のノード全体の集合を V、 MST を属するノードの集合を T、 とし、各ノードに値 cost, pi を割り当てます。
1.	初期状態で、T は空です。
	G(V, E) から任意のノード r を選び、   cost[r] = 0   pi[r] = -1 と初期化します。
2.	ノードの集合 V - T の中から、cost[u] が最も小さいノード u を選択します。
	u を T に追加すると同時に、u に隣接しかつ V - T に属する全てのノード v に対する値を以下のように更新します。
	もし、 エッジ (u, v) の重み ≦ cost[v] ならば、   cost[v] = エッジ (u, v) の重み   pi[v] = u
	この処理を T = V となるまで繰り返します。

(cost[v]、pi[v]) には、T に属するノード u と、V - T に属するノード v をつなぐエッジの中で、重みが最小のエッジの情報が記録されます。cost[v] には重みを、pi[v] には、ノード u、つまり MST におけるノード v の親が記録されます。従って、各ステップで、ノード u を選択するという操作は、「T に属するノードと V - T に属するノードをつなぐエッジの中で、重みが最小のもの」を選ぶ操作に相当します。 また、u が選ばれた時点で、エッジ ( u, pi[u] ) が MST を構成するエッジとなります。

001 int N;
002 int M[MAX][MAX];
003 
004 void prim(){
005     dist = 0.0;
006     
007     bool visited[MAX];
008     int cost[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < N; i++ ){
012         visited[i] = false;
013         cost[i] = INT_MAX;
014     }
015     
016     cost[0] = 0;
017     pi[0] = -1;
018     
019     while ( 1 ){
020         int mincost = INT_MAX;
021         int u;
022         // cost が最小となるノード u を選択する
023         for ( int i = 0; i < N; i++ ){
024             if ( !visited[i] && cost[i] < mincost ){
025                 mincost = cost[i];
026                 u = i;
027             }
028         }
029         
030         // すべてのノードが MST に含まれたとき
031         if ( mincost == INT_MAX ) break;
032         
033         visited[u] = true;
034         
035         for ( int v = 0; v < N; v++ ){
036             if ( visited[v] || M[u][v] == INT_MAX ) continue;
037             // 更新処理
038             if ( M[u][v] < cost[v] ){
039                 cost[v] = M[u][v];
040                 pi[v] = u;
041             }
042         }
043     }
044 }

最小全域木

Tree
木 (tree)とは、閉路をもたないグラフのことを言います。以下に例を示します。下図の左のグラフは、例えば、0 → 3 → 1 → 0 のような閉路をもつので、木ではありません。一方、残りの２つは、閉路をもたないグラフなので木です。 あるノード r から v まで、必ず１通りの path があります。



Spanning Tree
グラフ G(V, E) の極大木（spanning tree）G(V', E') とは、グラフの全ての頂点 V を含む部分グラフであって（V = V'）、木である限りできるだけ多くのエッジを持つものをいいます。グラフの極大木は、DFS または BFS で求めることができます。グラフの極大木は１つとは限りません。以下に、与えられたグラフの極大木の例を示します。



Minimum Spanning Tree
最小極大木 (minimum spanning tree)とは、与えられたグラフの極大木の中で、エッジの重みの総和が最小のものをいいます。以下に、与えられたグラフの最小極大木の例を示します。




最小極大木を求めることは、現実問題で非常に重要になり、多くの応用をもちます。例えば、グラフ G の各ノード u を都市とし、各エッジ (u, v) の重みを都市 u から都市 v への高速道路を建設する費用とすれば、G の最小全域木は、すべての都市を結ぶ高速道路網を可能な限り最小の費用で建設する解となります。

貪欲なアルゴリズム

多くの実用的なアルゴリズムは、「解の一部を選択する計算ステップの繰り返し」という構成になっています。Greedy Algorithm （貪欲アルゴリズム、よくばり法）は、各計算ステップで、局所的に最適（その時点で最も最適と思われるもの）な選択を繰り返し、最終的に大域的な最適解を求める方法です。

さらに一般化すると、Greedy Algorithm では、候補の集合 C、すでに選択された要素の集合 S、各ステップで、まだ選ばれていない候補の中から最適とされる要素を決定する選択関数 F、から成ります。最初は、選択された要素の集合 S は空で、その後１ステップごとに、候補の集合 C から選択関数 F によって決定された最適な要素を S に追加します。選択された要素は候補 C から取り除かれます。

例えば、これから紹介するグラフの最小全域木を求めるための Prim's Algorithm や Kruskal's Algorithm、グラフの単一始点最短経路を求めるための Dijkstra's Algorithm はGreedy Algorithm に分類されます。

この中でも、Prim's Algorithm と Dijkstra's Algorithm は同様の計算スキームをもち、以下のように動作します。

	グラフ G(V, E) のノード全体の集合を V、 問題の最適解を構成するノードの集合を T、 各ノード u に割り当てられる値を cost[u]、 とします。
1.	初期状態で、T は空であり、 T に追加するためのノードの候補の集合は V となります。
	任意の(または指定した)ノード s に対応する cost[s] の値を初期化します。
2.	各計算ステップで、cost の値を基に、 ノードの集合 V - T の中から最も良いとされるノード u を選択します。
	u を T に追加すると同時に、u に隣接しかつ T に含まれない全てのノード v に対する cost[v] を更新します。
	この処理を T = V となるまで繰り返します。