摘要：
本文首先最小生成樹三種算法簡單描述，再介紹Prim算法描述、算法正確性證明並給出例子，最後用C語言實現該算法，並給出測試結果。
一、最小生成樹算法
現實中不少問題可以抽象成最小生成樹模型，比如道路鋪設，使得任何兩個地方可達，並且使得總費用最省。最小生成樹算法主要有：
(1) Kruskal(克魯斯克爾)算法
從G中的最小邊開始，進行避圈式擴張。從符合擴展邊(新加入的邊不會構成回路)選擇權值最小的邊進行擴展。
(2) 管梅谷的破圈法
不斷破圈(從賦權圖G的任意圈開始，去掉該圈中權值最大的一條邊，稱為破圈)，直到G中沒有圈為止，最後剩下的G的子圖為G的最小生成樹。
(3) Prim算法
對於連通賦權圖G的任意一個頂點u，選擇與點u關聯的且權值最小的邊作為最小生成樹的第一條邊e1。在接下來的邊e2,e3,…,en-1 ,在與一條已經選取的邊只有一個公共端點的的所有邊中，選取權值最小的邊。
二、Prim算法
(1) 算法描述
Prim算法利用貪心法思想，算法描述如下：
在圖G=(V, E) （V表示頂點 ，E表示邊）中，從集合V中任取一個頂點（例如取頂點v0）放入集合 U中，這時 U={v0}，集合T(E)為空。
從v0出發尋找與U中頂點相鄰（另一頂點在V中）權值最小的邊的另一頂點v1，並使v1加入U。即U={v0,v1 }，同時將該邊加入集合T(E)中。
重復(2)，直到U = V為止。
這時T(E)中有n-1條邊，T = (U, T(E))就是一棵最小生成樹。
(2) 算法正確性證明
即證明用該算法得到的生成樹是最小的。如下：
設prim生成的樹為G0，假設存在Gmin使得cost(Gmin)<cost(G0)，則在Gmin中存在(u,v)不屬於G0，將(u,v)加入G0中可得一個環，且(u,v)不是該環的最長邊，這與prim每次生成最短邊矛盾。故假設不成立，命題得證[1]。
(3) 例子