# 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 $$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$$