最小全域木問題をプリムのアルゴリズムと隣接行列で解く

最小全域木問題をプリムのアルゴリズムと隣接行列を使って解きたいとおもいます。 問題はALDS_1_12_A:Minimum Spanning Treeを参照してください。

プリム法

プリムのアルゴリズムを使って、最小全域木(MST)を求めるには、以下の通りに行います。

グラフG = (V,E)の頂点全体の集合をV,MSTに属する頂点の集合をTとする
1.Gから任意の頂点rを選らんで、それをMSTのルートとしてTに追加する。
2.以下の処理をT=Vになるまで繰り返す

Tに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小のものである辺(p(u),u)を選び、
それをMSTの辺とし、uをTに追加する

上を実行する過程がプリム法のwikipediaの図に詳しくまとめられていたので、そちらを見るとわかりやすいと思います。

ここで、最小の重みの辺を保持するために、以下の変数を用います。
ここで、頂点の数n = |V|とします。

gColor[n] : color[v]にvへの訪問状態を色で記録します。
WHITE:未訪問,GRAY:訪問(未確定),BLACK(最小値決定済み)

gMatrix[n][n] : gMatrix[u][v]にuからvへの辺の重みを記録した隣接行列

weight[n] : weight[v]にTに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する

parent[n] : parent[v]にMSTにおける頂点vの親を記録する

プリムのアルゴリズムのコード

では、コードを見ていきます。
実施していく過程はwikiの図を見るとわかりやすいと思います。

#define MAX 100
#define INFTY 1 << 21
// 未訪問状態
#define WHITE 0
#define GRAY 1
#define BLACK 2

// 隣接行列
int gMatrix[MAX][MAX];

int prim(int n){
    // 頂点
    int u;
    // 最小の重み
    int minV;
    // Tに属する頂点と(V - T)に属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する
    int weight[MAX];
    // MSTにおける頂点vの親を記録する
    int parent[MAX];
    // 訪問状態を記録する
    int color[MAX];
    // 初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        parent[i] = -1;
        color[i] = WHITE;
    }
    // 初回探索地点をindex0にする
    weight[0] = 0;
    
    while(1){
        minV = INFTY;
        u = -1;
        // 隣接する地点で
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                // 最小の重みを記録する
                u = i;
                minV = weight[i];
            }
        }
        // 全て訪問した
        if(u == -1)break;
        // 訪問済み
        color[u] = BLACK;
        for(int v = 0;v < n;++v){
            // uとvの間に辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                if(weight[v] > gMatrix[u][v]){
                    // 隣接する辺に重みを割り当てる
                    weight[v] = gMatrix[u][v];
                    parent[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0;i < n;++i){
        if(parent[i] != -1) sum += gMatrix[i][parent[i]];
    }
    
    return sum;
}

O記法を考える

隣接行列を使ったプリムのアルゴリズムは
重みが最小である頂点を探すために、グラフの頂点数調べる必要があるので、
O(|V|^2)のアルゴリズムになります。

では、ALDS_1_12_A:Minimum Spanning Tree
を例題とした全体のコードです。

#include 
using namespace std;

#define MAX 100
#define INFTY 1 << 21
// 未訪問状態
#define WHITE 0
#define GRAY 1
#define BLACK 2

// 隣接行列
int gMatrix[MAX][MAX];

int prim(int n){
    // 頂点
    int u;
    // 最小の重み
    int minV;
    // Tに属する頂点と(V - T)に属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する
    int weight[MAX];
    // MSTにおける頂点vの親を記録する
    int parent[MAX];
    // 訪問状態を記録する
    int color[MAX];
    // 初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        parent[i] = -1;
        color[i] = WHITE;
    }
    // 初回探索地点をindex0にする
    weight[0] = 0;
    
    while(1){
        minV = INFTY;
        u = -1;
        // 隣接する地点で
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                // 最小の重みを記録する
                u = i;
                minV = weight[i];
            }
        }
        // 全て訪問した
        if(u == -1)break;
        // 訪問済み
        color[u] = BLACK;
        for(int v = 0;v < n;++v){
            // uとvの間に辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                if(weight[v] > gMatrix[u][v]){
                    // 隣接する辺に重みを割り当てる
                    weight[v] = gMatrix[u][v];
                    parent[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0;i < n;++i){
        if(parent[i] != -1) sum += gMatrix[i][parent[i]];
    }
    
    return sum;
}

int main(){
    int n;
    cin >> n;
    
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            int edge;
            cin >> edge;
            gMatrix[i][j] = (edge == -1) ? INFTY : edge;
        }
    }
    
    cout << prim(n) << endl;
    return 0;
}

参考