代碼顯示有問(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ò)程圖: