4.3.2 - Prim's algorithm

$G=(V, E)，V=\{1,2,...,v\}，U=\{1\}$

Steps:

1. 從起點開始，挑出最小成本的邊 $(u,v)，u∊U，v∊V-U$

2. $(u,v)$加入 $S$中，將 $v$加入 $U$中

3. 重複1~2直到 $V=U$ 或是無邊可挑

若 $S$的邊數小於 $v-1$ ，則 $G$ 無spanning tree。

This is pseudo code in C.
void prim(G, W, start){
    // G: adjacency matrix
    // W: the weight set of edges in graph
    // start: the start point
    // initial
    struct vertex node[NUM_NODES];
    for (int u = 0; u < NUM_NODES, u++){
        node[u].key = INT_MAX;
        node[u].pi = -1;
    }
    node[start].key = 0;
    create_priority_queue(q, node); //依照key值放入頂點
    // prim's
    while(!IsEmpty(q)){
        int u = dequeue(q);
        for (int v = 0; v<NUM_NODES; v++){
            //確認(u,v)邊存在，v在Queue中，(u,v)邊的權重小於v的key值
            if (G[u][v] == 1 && find(v) && W[u][v]<node[v].key){
                node[v].pi = u;
                node[v].key = W[u][v];
            }
        }
    }
}

• Time Complexity: $O(V^2)$

  使用Binary Heap、Fibnacci Heap可得更低時間。

e.g.

$U=\{1\},\ V-U=\{2,3,4,5,6,7\}\\ (u,v):(1,6), (1,2)\Rightarrow (1,6)$

$U=\{1,6\},V-U=\{2,3,4,5,7\}\\ (u,v):(1,2),(5,6) \Rightarrow(5,6)$

$U=\{1,5,6\},V-U=\{2,3,4,7\}\\ (u,v):(1,2),(5,7),(4,5) \Rightarrow (4,5)$

$U=\{1,4,5,6\}, V-U=\{2,3,7\}\\ (u,v)=(1,2),(5,7),(4,7),(3,4)\Rightarrow (3,4)$

$U=\{1,3,4,5,6\}, V-U=\{2,7\}\\ (u,v)=(1,2),(5,7),(4,7),(2,3)\Rightarrow (2,3)$

$U=\{1,2,3,4,5,6\}, V-U=\{7\}\\ (u,v)=(1,2),(5,7),(4,7),(2,7)\Rightarrow (2,7)$

$U=\{1,2,3,4,5,6,7\}, V-U=\{\}\Rightarrow end$