(原創(chuàng))最小生成樹之Prim(普里姆)算法+代碼詳解,最懂你的講解

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


謝謝大嘎

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市鲜屏,隨后出現(xiàn)的幾起案子烹看,更是在濱河造成了極大的恐慌,老刑警劉巖洛史,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件惯殊,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡也殖,警方通過(guò)查閱死者的電腦和手機(jī)靠胜,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人浪漠,你說(shuō)我怎么就攤上這事■郑” “怎么了址愿?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)冻璃。 經(jīng)常有香客問(wèn)我响谓,道長(zhǎng),這世上最難降的妖魔是什么省艳? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任娘纷,我火速辦了婚禮,結(jié)果婚禮上跋炕,老公的妹妹穿的比我還像新娘赖晶。我一直安慰自己,他們只是感情好辐烂,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布遏插。 她就那樣靜靜地躺著,像睡著了一般纠修。 火紅的嫁衣襯著肌膚如雪胳嘲。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天扣草,我揣著相機(jī)與錄音了牛,去河邊找鬼。 笑死辰妙,一個(gè)胖子當(dāng)著我的面吹牛鹰祸,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播上岗,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼福荸,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了肴掷?” 一聲冷哼從身側(cè)響起敬锐,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎呆瞻,沒(méi)想到半個(gè)月后台夺,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡痴脾,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年颤介,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡滚朵,死狀恐怖冤灾,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情辕近,我是刑警寧澤韵吨,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站移宅,受9級(jí)特大地震影響归粉,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜漏峰,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一糠悼、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧浅乔,春花似錦倔喂、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至顾复,卻和暖如春班挖,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背芯砸。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工萧芙, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人假丧。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓双揪,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親包帚。 傳聞我的和親對(duì)象是個(gè)殘疾皇子渔期,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 圖的定義與術(shù)語(yǔ) 1、圖按照有無(wú)方向分為無(wú)向圖和有向圖渴邦。無(wú)向圖由頂點(diǎn)和邊構(gòu)成疯趟,有向圖由頂點(diǎn)和弧構(gòu)成∧彼螅弧有弧尾和弧頭之...
    unravelW閱讀 411評(píng)論 0 0
  • 在C語(yǔ)言中,五種基本數(shù)據(jù)類型存儲(chǔ)空間長(zhǎng)度的排列順序是: A)char B)char=int<=float C)ch...
    夏天再來(lái)閱讀 3,352評(píng)論 0 2
  • 1)這本書為什么值得看: Python語(yǔ)言描述信峻,如果學(xué)的Python用這本書學(xué)數(shù)據(jù)結(jié)構(gòu)更合適 2016年出版,內(nèi)容...
    孫懷闊閱讀 12,506評(píng)論 0 15
  • 不喜歡這樣的焦慮瓮床,來(lái)探討存在的意義盹舞,在自我的世界产镐,開始懷疑自己! 等待的時(shí)間總是煎熬踢步,煎熬的過(guò)程產(chǎn)生無(wú)奈癣亚,在無(wú)奈嘆...
    麥穗姑娘閱讀 224評(píng)論 0 0
  • 《夏洛特?zé)馈愤@部影片很多人都看過(guò),里面劇情也不陌生贾虽。很多人都說(shuō)因?yàn)橄穆宀粍诙@逃糟,不是靠自己奮斗得來(lái)的成功,所...
    一枚音符閱讀 480評(píng)論 0 3