貪心過程.
首先,把圖中的點(diǎn)分成兩種,已連通和未連通的,我把它們分別稱為"黑"和"白"點(diǎn).
一開始時(shí),圖中全是白點(diǎn),沒有黑點(diǎn).算法的第一步,隨機(jī)選出一個(gè)白點(diǎn),染成黑色.
然后開始一個(gè)重復(fù)的過程:
從當(dāng)前圖的邊中尋找這樣的一些邊:它的其中一個(gè)端點(diǎn)是黑點(diǎn),而另一個(gè)端點(diǎn)是一個(gè)白點(diǎn). 我們可以把這類邊稱為"可擴(kuò)展邊". 然后算法需要從所有的可擴(kuò)展邊之中選出權(quán)值最小的一條.把這條可擴(kuò)展邊加入生成樹之中,且把這條邊的白色端點(diǎn)染成黑色.

重復(fù)這個(gè)過程,直到全部的節(jié)點(diǎn)都為黑色.

算法可以優(yōu)化的地方是,在選擇權(quán)值最小的可行邊時(shí)可以使用堆.

G=（V,E）
①初始化：讀入的數(shù)據(jù)用鄰接矩陣x存儲(chǔ)，一個(gè)一維布爾型數(shù)組chosen，記錄第i個(gè)節(jié)點(diǎn)是否已選，初始值除1外全部設(shè)為false，記錄權(quán)值的變量cost賦值為0；
以下②到④循環(huán)執(zhí)行v-1次（每次生成一條邊，運(yùn)行（點(diǎn)的個(gè)數(shù)減1）次后，生成一棵最小生成樹）：
②臨時(shí)變量p賦值為無限大，用于記錄當(dāng)前最小值；
③二重循環(huán)（外循環(huán)i，內(nèi)循環(huán)j）掃描鄰接矩陣：如果chosen[i]=true（也就是說第i個(gè)點(diǎn)已選），那么掃描x[i]，如果not(chosen[j])（也就是說第j個(gè)點(diǎn)未選），那么如果x[i,j]<p，那么p賦值為x[i,j],臨時(shí)變量q賦值為j;
④把cost賦值為cost+o，把chosen[q]賦值為true（也就是說第j個(gè)點(diǎn)已選）；
⑤輸出cost。

一、以上給出具體的運(yùn)行過程。這個(gè)算法的策略就是貪心，和dijkstra差不多，每次都選擇未選的邊中權(quán)值最小的那一條，直到生成最小生成樹。用chosen的目的就是保證生成過程中沒有環(huán)出現(xiàn)，也就是說保證選擇的邊不會(huì)通向一個(gè)已經(jīng)包含在生成樹中的點(diǎn)。
二、這個(gè)只輸出最小生成樹的每條邊權(quán)值之和，如果要輸出整棵最小生成樹，加一個(gè)[1..n,1..2]的數(shù)組，在第④步的時(shí)候把每次選的邊記錄下來就可以了。
三、用小頂堆在第③步優(yōu)化一下的話就不用每次都掃描那么多邊了，只不過建堆維護(hù)堆代碼寫起來很麻煩。
四、prim適合用于比較稠密的網(wǎng)，點(diǎn)數(shù)和邊數(shù)差不多的時(shí)候效率很惡心，一般都用kruskal。