# 4.3.2 - Prim's algorithm

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

Steps:

1. 從起點開始，挑出最小成本的邊 $$(u,v)，u∊U，v∊V-U$$&#x20;
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.&#x20;

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIpnrR8j8h5zSGnE3TX%2F-LIpo1kkcpkN8J3_YPvK%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-01%2015.19.21.jpg?alt=media&#x26;token=1ffb1e86-7633-49b0-91ef-d668e91da314" alt="" data-size="original">&#x20;

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

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIpnrR8j8h5zSGnE3TX%2F-LIsS5p3voBdmZR8gC2w%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-01%2015.36.31.jpg?alt=media&#x26;token=cb1fe4f6-aa0e-4d38-8ccb-75801f4f74c9" alt="" data-size="original">&#x20;

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

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIsTI1rImP8FoPLpskw%2F-LIsUeu4cHxZvl3EQ4tp%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-02%2010.36.33.jpg?alt=media&#x26;token=56afacae-8f82-4e55-96c5-46f341e1d495" alt="" data-size="original">&#x20;

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

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIsTI1rImP8FoPLpskw%2F-LIsV53J8Q4w6Wh3NcdF%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-02%2010.38.20.jpg?alt=media&#x26;token=da667ef1-18cd-42e5-832c-09273d0dfe7d" alt="" data-size="original">&#x20;

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

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIsVZKA_9SsV9yJSwoE%2F-LIsVaTDw3JgauyWLsDT%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-02%2010.40.37.jpg?alt=media&#x26;token=9c7edaa1-05a8-4454-938a-0c4d607a028f" alt="" data-size="original">&#x20;

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

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIsVZKA_9SsV9yJSwoE%2F-LIsW0G3VSjOjHKZ6LWx%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-02%2010.42.32.jpg?alt=media&#x26;token=221851fb-de99-49b2-9f46-75ee8cf1c2b8" alt="" data-size="original">&#x20;

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

<img src="https://2769815795-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGckN3OAfinKuVIrkMj%2F-LIpnrR8j8h5zSGnE3TX%2F-LIsSi4WwlGei4o4ftvc%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-01%2015.45.52.jpg?alt=media&#x26;token=b058375d-e247-4207-ba9a-160ecba70325" alt="" data-size="original">&#x20;

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