Minimum Spanning Tree:Prim's Algorithm

Posted by Chiu CC on 2 25, 2016


先備知識與注意事項

本篇文章要接著介紹另一個尋找MST的演算法:Prim's Algorithm

建議讀者可以先閱讀在Minimum Spanning Tree:Intro(簡介)介紹過的「演算法概念」與Theorem1Corollary2,對理解接下來的內容會有些幫助。


目錄


Prim's Algorithm

考慮圖一(a)的Graph,目標是要在此Graph上找到MST。

cc

圖一(a)。

Prim's Algorithm之演算法將使用三個資料項目:

  • predecessor[]:記錄最後在MST中,各個vertex之間的「parent-child」關係。
  • key[]:此為「挑選edge」的關鍵,key[]記錄的會是edge的weight,但是會將weight「暫存在vertex上」,表示「到達該vertex的成本」,演算法的最後將挑選出能夠以「最低成本」抵達該vertex的edge,此edge上的兩個vertex即形成「parent-child」關係,能夠記錄進predecessor[]
  • visited[]:用來標記出,哪些vertex已經在MST裡面,哪些還沒有。已經是MST之vertex標記為\(1\),其餘為\(0\)

有了key[]visited[],就能正確挑選出edge,形成最後的MST。

演算法步驟如下:

首先,初始化所有vertex的資料項目,見圖一(b):

  • predecessor[]設成\(-1\),表示vertex沒有predecessor。
  • key[]設成「無限大」,表示所有vertex都沒有辦法經由與其餘vertex相連之edge抵達。
  • visited[]設成\(0\),表示MST裡面還沒有vertex。
    (程式範例中,visited[]的資料型態是用bool,因此設為false)

cc

圖一(b)。

初始化之後,選定其中一個vertex作為起點。
這個起點會是MST的root,如果不要求MST之起點為何,那麼起點可以任意挑選。
在此選定vertex(2)作為起點,便將key[2]設成\(0\)

  • 更新key[]是關鍵,原因在於,演算法會根據key[]的大小,每次挑選出key[]值最小的vertex放進MST。

接著便開始演算法的主要迴圈。

  • 先從key[]中挑選出數值最小(可以想成「抵達成本」最小)的vertex,放進MST。
    在此挑選到的是vertex(2),見圖一(c)。
  • 由於vertex(2)已經屬於MST,便更新visited[2]=1

cc

圖一(c)。

接著,找到所有與vertex(2)具有edge相連的vertex(X),比較所有edge(2,X)之weight與vertex(X)的key[],如果weight比key[X]小,便更新predecessor[X]成vertex(2),並且把key[X]更新成weight(2,X):

  • 表示從vertex(2)經由edge(2,X)抵達vertex(X),只要花費weight(2,X)的成本,而到最後,若Graph上沒有從其他vertex經由「成本更小的edge」能夠抵達vertex(X),那麼MST中,就會存在edge(2,X),因為在所有連結vertex(2)與vertex(X)的edge中,edge(2,X)的成本最低。
  • 另外一種情況,若weight(2,X)比key[X]大,那就不更新key[X],表示從Graph中某個vertex(Y)到達vertex(X),會比從vertex(2)到達vertex(X)的成本更低。也不更新predecessor[X],維持vertex(Y)作為vertex(X)的predecessor。

根據圖一(c),與vertex(2)相連的vertex分別是vertex(1)、vertex(3)、vertex(6),經比較後發現:

  • \(weight(2,1)<\)key[1]
  • \(weight(2,3)<\)key[3]
  • \(weight(2,6)<\)key[6]

此時便更新key[]predecessor[],見圖一(d):

  • key[1]=weight(2,1)=10predecessor[1]=2
  • key[3]=weight(2,3)=5predecessor[3]=2
  • key[6]=weight(2,6)=3predecessor[6]=2

cc

圖一(d)。

總結圖一(c)與圖一(d)的步驟:

  1. 選取key[]值最小的vertex放進MST,假設為vertex(X);
  2. 將vertex(X)之visited[]標記為\(1\)(或是true);
  3. 比較weight與key[],判斷是否需要更新所有與vertex(X)具有edge相連之vertex的key[]predecessor[]

以上便完成一次Prim's Algorithm的主要迴圈。
若Graph上有\(V\)個vertex,接下來只要繼續上述步驟「\(V-1\)」次,就能得到Graph上的MST。

接著,繼續從key[]挑選出數值最小的vertex(3)放進MST,更新visited[3]=1,見圖一(e)。

cc

圖一(e)。

再比較所有與vertex(3)具有edge相連之vertex的key[],根據圖一(e):

  • vertex(2)已經進入MST中(visited[2]=1),忽略不計;
  • vertex(6)與vertex(3)相連,不過weight(6,3)比key[6]=8還要大,表示從vertex(3)走到vertex(6)之成本高於從vertex(2)走到vertex(6),因此不更新key[6]predecessor[6]
  • vertex(4)與vertex(3)相連,並且weight(4,3)\(<\)key[4]=infinity,於是更新key[4]=weight(4,3)predecessor[4]=3,見圖一(f)。

cc

圖一(f)。

接著重複上述步驟,直到Graph上所有vertex都被放進MST中(visited[]全部變成\(1\)),即可找到MST,見圖一(g)至圖一(n)。

cc

圖一(g):將vertex(4)放進MST中visited[4]=1

cc

圖一(h):從vertex(4)探索vertex(1)、vertex(5)、vertex(6)。
更新vertex(1)、vertex(5)、vertex(6)之key[]predecessor[]

cc

圖一(i):將vertex(1)放進MST中visited[1]=1

cc

圖一(j):從vertex(1)探索vertex(0)、vertex(2)、vertex(4)、vertex(6)。
更新vertex(0)的key[]predecessor[]

cc

圖一(k):將vertex(6)放進MST中visited[6]=1

cc

圖一(l):將vertex(0)放進MST中visited[0]=1

cc

圖一(m):從vertex(0)探索vertex(1)、vertex(5)。
更新vertex(5)的key[]predecessor[]

cc

圖一(n):將vertex(5)放進MST中visited[5]=1MST建立完畢。

見圖一(n),當Graph上所有vertex的visited[]都被設為\(1\)(或是true)後,MST便建立完畢。

那麼Prim's Algorithm的運作原則是什麼?

觀察圖一(d)至圖一(j),被放進MST的vertex恰好都與vertex(6)有edge相連,因此,vertex(6)總共被「檢查了四次」(比較weight與key[6]四次),並且「更新了兩次」(key[6]\(\infty\)更新成\(8\),最後更新成\(2\)),可以肯定的是,若vertex(6)一定要與Graph中的其中一個vertex相連(這是MST的要求),那麼Prim's Algorithm一定能夠替vertex(6)挑選出最小weight的edge:

  • 以圖一(n)為例,vertex(6)共有四條edge連結至其他vertex,而最後是透過weight為\(2\)的edge(4,6)與vertex(4)相連。

再看圖二,當vertex(3)被放進MST時,vertex(2)已經被放進MST,因此可以把這兩個vertex視為一個connected component,並且找到一個Cut \((C,V-C)\),其中\(C=\){\(2,3\)},\(V-C=\){\(0,1,4,5,6\)},而在Cut上的crossing edge總共有:

  • edge(1,2),weight\(=10\)
  • edge(2,6),weight\(=8\)
  • edge(3,6),weight\(=9\)
  • edge(3,4),weight\(=7\)

顯然,light edge為edge(3,4),因此edge(3,4)必定會是MST中的edge。

這便是Theorem1所證明的事。

cc

圖二。


程式碼

以下的程式範例包含了class Graphmain()

class Graph:使用Adjacency Matrix而不是Adjacency List

PrimMST()為主要演算法,內容如前一節所介紹。

MinKeyExtract()根據visited找到,所有尚未放進MST的vertex中,key[]最小值的vertex。

最後,main()利用AddEdge()建立出Graph的AdjMatrix,並執行PrimMST()

// C++ code
#include <iostream>
#include <vector>
#include <iomanip>      // for setw()

const int Max_Weight = 1000;    // 初始化key[]時需要infinity, 以Max_Weight代替

class GraphMST{
private:
    int num_vertex;
    std::vector<std::vector<int>> AdjMatrix;
public:
    GraphMST():num_vertex(0){};
    GraphMST(int n):num_vertex(n){
        AdjMatrix.resize(num_vertex);
        for (int i = 0; i < num_vertex; i++) {
            AdjMatrix[i].resize(num_vertex);
        }
    }
    void AddEdge(int from, int to, int weight);

    void PrimMST(int Start = 0);        // 可以指定起點Start, 若沒有指定, 則從vertex(0)作為MST的root
    friend int MinKeyExtract(int *key, bool *visited, int size);
};

int MinKeyExtract(int *key, bool *visited, int size){

    int min = Max_Weight, min_idx = 0;
    for (int i = 0; i < size; i++) {
        if (visited[i]==false && key[i]<min) {
            min = key[i];
            min_idx = i;
        }
    }
    return min_idx;
}
void GraphMST::PrimMST(int Start){

    int key[num_vertex], predecessor[num_vertex];
    bool visited[num_vertex];

    for (int i = 0; i < num_vertex; i++) {
        key[i] = Max_Weight;
        predecessor[i] = -1;
        visited[i] = false;     // false表示vertex還沒有被visited
    }

    key[Start] = 0;
    for (int i = 0; i < num_vertex; i++) {
        int u = MinKeyExtract(key, visited, num_vertex);
        visited[u] = true;
        for (int i = 0; i < num_vertex; i++) {
            if ( visited[i]==false && AdjMatrix[u][i]!=0 && AdjMatrix[u][i]<key[i]) {
                predecessor[i] = u;
                key[i] = AdjMatrix[u][i];
            }
        }
    }
    // print MST, 與MST演算法主體無關
    std::cout << std::setw(3) << "v1" << " - " << std::setw(3) << "v2"<< " : weight\n";
    int i = (Start+1)%num_vertex;   // 若從4開始, i依序為5,6,0,1,2,3
    while (i != Start) {
        std::cout << std::setw(3) << predecessor[i] << " - " << std::setw(3) << i
                  << " : " << std::setw(4) << AdjMatrix[predecessor[i]][i] <<"\n";
        i = (++i)%num_vertex;       // 到了6之後, 6+1 = 7, error:bad_access, 透過mod把7喬回0
    }
}
void GraphMST::AddEdge(int from, int to, int weight){
    AdjMatrix[from][to] = weight;
}

int main(){

    GraphMST g6(7);
    g6.AddEdge(0, 1, 5);g6.AddEdge(0, 5, 3);
    g6.AddEdge(1, 0, 5);g6.AddEdge(1, 2, 10);g6.AddEdge(1, 4, 1);g6.AddEdge(1, 6, 4);
    g6.AddEdge(2, 1, 10);g6.AddEdge(2, 3, 5);g6.AddEdge(2, 6, 8);
    g6.AddEdge(3, 2, 5);g6.AddEdge(3, 4, 7);g6.AddEdge(3, 6, 9);
    g6.AddEdge(4, 1, 1);g6.AddEdge(4, 3, 7);g6.AddEdge(4, 5, 6);g6.AddEdge(4, 6, 2);
    g6.AddEdge(5, 0, 3);g6.AddEdge(5, 4, 6);
    g6.AddEdge(6, 1, 4);g6.AddEdge(6, 2, 8);g6.AddEdge(6, 3, 9);g6.AddEdge(6, 4, 2);

    std::cout << "MST found by Prim:\n";
    g6.PrimMST(2);

    return 0;
}

output:

MST found by Prim:
 v1 -  v2 : weight
  2 -   3 :    5
  3 -   4 :    7
  0 -   5 :    3
  4 -   6 :    2
  1 -   0 :    5
  4 -   1 :    1

結果如同圖一(n):

cc

圖一(n)。


若參考Introduction to Algorithms, Ch23所提供的Prim's Algorithm之虛擬碼(pseudo code),將會發現其中有個「Min-Priority Queue」的資料結構,如果讀者有興趣,可以參考以下連結(筆者還在磨劍,請見諒):

以上便是利用Prim's Algorithm尋找MST之介紹。
若讀者能夠花些時間比較這兩種種樹的策略,將會發現,兩邊都是天才啊。



參考資料:


MST系列文章

Minimum Spanning Tree:Intro(簡介)
Minimum Spanning Tree:Kruskal's Algorithm
Minimum Spanning Tree:Prim's Algorithm
Minimum Spanning Tree:Prim's Algorithm using Min-Priority Queue

回到目錄:

目錄:演算法與資料結構