代碼顯示有問(wèn)題，可移步博客園：https://www.cnblogs.com/yx1999/p/10357626.html
Prim算法
（哈欠）在創(chuàng)建最小生成樹之前，讓我們回憶一下什么是最小生成樹秽荤。最小生成樹即在一個(gè)待權(quán)值的圖（即網(wǎng)結(jié)構(gòu)）中用一個(gè)七拐八繞的折線串連起所有的點(diǎn)，最小嘛柠横，顧名思義窃款，要權(quán)值相加起來(lái)最小，你當(dāng)然可以拿起筆來(lái)就算你腦中的每一種可能牍氛，但是如果你了解了這種算法晨继，你就能跟我一樣，一次畫出完美答案搬俊。
上個(gè)栗子：
我先說(shuō)一哈這個(gè)算法的方法論踱稍，然后我們來(lái)代碼實(shí)現(xiàn)一下，在講解開始之前悠抹，敲黑板，記得我們要生成一個(gè)權(quán)值最小的樹扩淀，所以每一步都要考慮到樹的每一個(gè)結(jié)點(diǎn)楔敌，不要孤立地用一個(gè)結(jié)點(diǎn)來(lái)對(duì)比從而走上死路，我們?nèi)芜x一個(gè)點(diǎn)開始生成驻谆，教材里選的 v0卵凑，那我們就選 v8庆聘，戰(zhàn)斗開始
v8 有三條路，分別通往v1 v2 v3勺卢，v2那條路權(quán)值最小伙判，ok， v2→v8黑忱，然后我們?cè)摽词裁囱绺В绻阏f(shuō)找和 v2 相鄰的 v8 以外的邊，那我剛才的強(qiáng)調(diào)就gg了甫煞，我們找v2 和 v8除相連的線之外的所有分支菇曲，易得 v8→v1的權(quán)值最小，ok抚吠，下一步找哪幾個(gè)點(diǎn)常潮？v2 v1 v8這三個(gè)點(diǎn)除兩條連接線以外的所有分支，挑最小的那一條楷力，后面重復(fù)前面的操作喊式，每次都把新加入的伙伴算在找線之內(nèi)才對(duì)，自己畫一下給答案：
操作一遍是不是發(fā)現(xiàn)還真的跟哪個(gè)點(diǎn)開始沒(méi)雞兒關(guān)系萧朝，因?yàn)槊總€(gè)點(diǎn)都要連到岔留，關(guān)鍵就在于沿最小分支找點(diǎn)的時(shí)候一定要把它看成一個(gè)樹結(jié)構(gòu)來(lái)找，才算是最小生成樹剪勿。
還是給一下標(biāo)準(zhǔn)定義：
我們把構(gòu)造連通網(wǎng)的最小代價(jià)（權(quán)值）生成樹 稱為最小生成樹 （Minimum Cost Spanning Tree）贸诚。
方法論就到這里，相信下一次看到同樣的現(xiàn)實(shí)問(wèn)題厕吉，你也應(yīng)該能在第一時(shí)間用正確的思路找到合適的路酱固。
在代碼實(shí)現(xiàn)之前，我們先請(qǐng)來(lái)連通圖的好基友——鄰接矩陣
我們發(fā)現(xiàn)一行一行的矩陣很容易顯示權(quán)值头朱，這樣就可以快速對(duì)比權(quán)值的大小运悲，只要在循環(huán)的每一步留存下權(quán)值較小的邊權(quán)值和頂點(diǎn)下標(biāo)，就可以實(shí)現(xiàn)项钮。
和以前一樣班眯，我們還是用 INFINITY 來(lái)表示無(wú)限大，即不存在該邊
代碼如下：
?void MiniSpanTree_Prim(MGragh G)
?{
? ? int mini,i,j,k;
? ? int adjvex[MAXVEX]; //保存相關(guān)頂點(diǎn)下標(biāo)
? ? ?int lowcost[MAXVEX]; //保存相關(guān)頂點(diǎn)間邊的權(quán)值
? ? lowcost[0] = 0;//這里把第0位的權(quán)值置0表示v0已加入生成樹
? ? //ps：lowcost[i] = 0 表示i那個(gè)下標(biāo)的頂點(diǎn)加入生成樹
? ? adjvex[0] = 0; //初始化第一個(gè)頂點(diǎn)的下標(biāo)為0
? ? for(i = 0; i < G.numVertexes; i++)
? ? {
? ? ? ? lowcost[i] = G.arc[0][i];//將vo相關(guān)頂點(diǎn)的權(quán)值存入lowcost數(shù)組
? ? ? ? adjvex[i] = 0;//置所有下標(biāo)為v0
? ? }
? ? for(i = 1; i < G.numVertexes; i++) //最小生成樹開始遼
? ? {
? ? ? ? mini = INFITINY; //先把權(quán)值的最小值置為無(wú)限大
? ? ? ? j = 1;
? ? ? ? k = 0;
? ? ? ? while(j < G.numVertexes)
? ? ? ? {
? ? ? ? ? ? if(lowcost[j] != 0 && lowcost[j] < mini)//判斷并向lowcost中添加權(quán)值
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mini = lowcost[j];
? ? ? ? ? ? ? ? k = j;
? ? ? ? ? ? }
? ? ? ? ? ? j++;
? ? ? ? }
? ? ? ? printf("(%d %d)",lowcost[k],k);
? ? ? ? lowcost[k] = 0;//置0表示這個(gè)定點(diǎn)已經(jīng)完成任務(wù)烁巫，找到最小權(quán)值分支
? ? ? ? for(j = 1; j < G.numVertexes; j++)
? ? ? ? {
? ? ? ? ? ? if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? lowcost[j] = G.arc[k][j];
? ? ? ? ? ? ? ? adjvex[j] = k;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
簡(jiǎn)單講解一哈：
4~5行署隘，先說(shuō) adjvex[] ，這個(gè)數(shù)組要解決的問(wèn)題就是存入已經(jīng)安排好的那些頂點(diǎn)的下標(biāo)亚隙，什么叫安排好了呢磁餐，比如我已經(jīng)找到了 v0→v1 ，v1 就可以算是安排好了阿弃，而v0點(diǎn)置0則算做初始化的操作诊霹；再說(shuō) lowcost[] 這個(gè)數(shù)組羞延，聽名字就是最小權(quán)值的意思，下面講循環(huán)的時(shí)候詳解這個(gè)東西到底儲(chǔ)存了些什么脾还，然后每次更新之后能做什么
6~13行完全是初始化伴箩，要注意的是就是 lowcost[] 儲(chǔ)存了鄰接矩陣 v0 這一行的權(quán)值
14~38行是最小生成樹的整體代碼
16行就是每次都把最小值重置
19~27行，從 1 開始遍歷完全鄙漏，找到現(xiàn)在這個(gè)狀態(tài)下的最小權(quán)值數(shù)嗤谚，并且把這個(gè)下標(biāo)用 k 存住，28行就是把權(quán)值和下標(biāo)打印出來(lái)泥张，當(dāng)然也可以換成別的操作呵恢，這里不再贅述
?然后29行，看看他都干了些什么媚创，它把? adjvex[ k ] 置0渗钉，看一下第一點(diǎn)，這里表示 v1 完成任務(wù)钞钙，沒(méi)有利用價(jià)值了
然后30~37這個(gè)循環(huán)鳄橘，看看循環(huán)的條件，條件一：??lowcost[ j ] != 0芒炼，這是啥意思瘫怜，表示在沒(méi)有完成任務(wù)的頂點(diǎn)中選擇，條件二：?G.arc[k][j] < lowcost[j]? ?這表示在剛才找到的新頂點(diǎn)的矩陣那一行去對(duì)應(yīng)本刽，如果有更小的權(quán)值就把 lowcost[] 更新掉鲸湃，這樣就保證了這個(gè)數(shù)組中同時(shí)存在好幾個(gè)頂點(diǎn)的權(quán)值信息，還是擇優(yōu)錄用的子寓，然后返回循環(huán)頭暗挑，再找這次的最小權(quán)值點(diǎn)，周而復(fù)始斜友。
時(shí)間復(fù)雜度 O（n2） 炸裆，沒(méi)啥問(wèn)題遼
最后附上過(guò)程圖：
