lxmgraphalgorithms

1、圖算法圖的遍歷l和樹的遍歷類似，在此，我們希望從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問一次。這一過程就叫做圖的遍歷(traversinggraph)。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。l通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。它們對(duì)無(wú)向圖和有向圖都適用。圖的遍歷：廣度優(yōu)先搜索 廣度優(yōu)先搜索(breadth-first search)遍歷類似于樹的按層次遍歷的過程。 假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)

2、的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通且路徑長(zhǎng)度為1，2，的頂點(diǎn)。圖的遍歷：廣度優(yōu)先搜索例子 例如，對(duì)右進(jìn)行廣度優(yōu)先搜索遍歷的過程如圖(c)所示，得到的頂點(diǎn)訪問序列為 v1-v2-v3-v4-v5-v6-v7-v8 v8v5v4v6v7v1v3v2v1v3v6v7v5v2v4v8(c)圖的遍歷：深度優(yōu)先搜索 深度優(yōu)先搜索(depth-first search)遍歷類似于樹的先

3、根遍歷，是樹的先根遍歷的推廣。 假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，則深度優(yōu)先搜索可從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。圖的遍歷：深度優(yōu)先搜索例子 以圖 (a)中無(wú)向圖為例，深度優(yōu)先搜索遍歷圖的過程如圖 (b)所示。 (a) 由此，得到頂點(diǎn)訪問序列為： v1-v2-v4-v8-v5-v3-v6-v7 (b)v8v5v4v6v7v1v3v2v5v8v7v6v4v3v2v1無(wú)向圖的dfs算法p

4、106v5v4v1v3v2v5v4v1v3v2(1)(2)(3)(4)(5)(6)(7) 對(duì)(a)圖，由dfs算法可得(b)圖有向樹（實(shí)線）和余數(shù)（虛線），箭頭表示搜索過程。 其中tree=(1),(2),(3),(5)， back=(4),(6),(7) num(v1)=1, num(v2)=2, num(v4)=3, num(v3)=4,num(v5)=5 后退邊的方向是從num值高的頂點(diǎn)到num值小的頂點(diǎn)； 樹枝邊的方向是從num值低的頂點(diǎn)到num值高的頂點(diǎn)。 若從頂點(diǎn)a到可以沿著dfs外向樹樹枝走到頂點(diǎn)b，則成a點(diǎn)為b點(diǎn)的祖先，b點(diǎn)為a點(diǎn)的子孫。無(wú)向圖的dfs算法p106(1)tree

5、=, back=,i=1.all v v 作【father(v)=0,mark(v)=0】(2)任選一點(diǎn)r滿足mark(r)=0,作【v=r,mark(v)=1,num(v)=i 】(3)若所有與v點(diǎn)關(guān)聯(lián)的邊均已給出標(biāo)志，則轉(zhuǎn)(5)；否則任選一未給標(biāo)志的邊(v,w)轉(zhuǎn)(4)。(4)給(v,w)邊以v到w的方向，并給以標(biāo)志*表示通過檢查。若mark(w)=0，則作【i+,num(w)=i,tree=tree u(v,w),mark(w)=1,father(w)=v,v=w ，轉(zhuǎn)(3) 】。若mark(w)=1，則作【back=back u (v,w) ，轉(zhuǎn)(3) 】(5)若father(v)!=

6、0，則作 【v=father(v)，轉(zhuǎn)(3)】； 否則作 【若all v v 恒有mark(v)=1， 則結(jié)束； 否則作 i+,轉(zhuǎn)(2) 】v5v4v1v3v2(1)(2)(3)(4)(5)(6)(7)有向無(wú)環(huán)圖的dfs算法p108 num(v1)=1, num(v2)=2, num(v3)=3, num(v4)=4, num(v5)=5, num(v6)=6, num(v7)=7,tree=(1),(2),(3),(7),(9)forward=(4),(5)cross=(8),(10)back=(11)v5v4v6v7v1v3v2v5v4v6v7v1v3v2(6)(1)(2)(3)(4)(5

7、)(7)(8)(9)(10)(11)圖的連通性：無(wú)向圖的連通性l 在簡(jiǎn)單無(wú)向圖g = (v, e)中, 若存在一條路連接vi和vj, 則稱頂點(diǎn)vi和vj是連接的。若g中任意兩個(gè)頂點(diǎn)均是連接的,則稱g是連通(connected)的,否則是不連通的或分離(separated)圖。l 在n階簡(jiǎn)單圖g, 如果對(duì)g的每對(duì)頂點(diǎn)u和v, deg(u) + deg(v) n1, 則g是連通圖。證明證明 假設(shè)假設(shè)g不連通不連通, 則則g至少有兩個(gè)分圖至少有兩個(gè)分圖。設(shè)其中一個(gè)分圖含有設(shè)其中一個(gè)分圖含有q個(gè)頂點(diǎn)個(gè)頂點(diǎn), 而其余各分圖共含有而其余各分圖共含有n q個(gè)頂點(diǎn)。個(gè)頂點(diǎn)。在這兩部分中各取一個(gè)頂點(diǎn)在這兩部分中

8、各取一個(gè)頂點(diǎn)u和和v, 則則0deg(u)q 1, 0deg(v)n q 1, 因此因此deg(u) + deg(v)n 2, 這與題設(shè)這與題設(shè)deg(u ) + deg(v)n 1矛盾。矛盾。圖的連通性：無(wú)向圖的連通性l 簡(jiǎn)單圖是連通的當(dāng)且僅當(dāng)它具有生成樹。l p94 無(wú)向圖的連通塊數(shù)目判斷算法(1) i=1, f=1(2) 若頂點(diǎn)vai和vbi同屬于一個(gè)連通塊時(shí)轉(zhuǎn)(6)；否則轉(zhuǎn)(3)。(3)若頂點(diǎn)vai和vbi都不屬于任何一個(gè)連通塊，則用邊ei=建立一新連通塊，f=f+1，轉(zhuǎn)(6)(4)若頂點(diǎn)vai(或vbi ) 屬于第p個(gè)連通塊，但 vbi(或vai )不屬于任何一個(gè)連通塊，則邊ei=也

9、屬于第p個(gè)連通塊，轉(zhuǎn)(6)(5)若頂點(diǎn)vai和vbi分別屬于不同的兩個(gè)連通塊，則用邊ei=使這兩個(gè)不同連通塊連成一個(gè)連通塊，f=f-1，轉(zhuǎn)(6)(6) i=i+1, 若i1, 而刪除了s的任一真子集后得到的子圖是連通圖, 則稱s是g的一個(gè)點(diǎn)割集(cut-set of node)。l 切割點(diǎn)：若v g，將v點(diǎn)及與v點(diǎn)關(guān)聯(lián)的所有的邊從g中消去，余下的圖的連通塊數(shù)目增加了，則稱v點(diǎn)為切割點(diǎn)。 (cut-point)l 互連通圖：無(wú)切割點(diǎn)的連通圖叫做互連通圖。l 互連通塊：圖g的最大的互連通圖叫做互連通塊。例例 在上圖中在上圖中v2, v7, v3, v4為為點(diǎn)割集點(diǎn)割集, v3, v4均為均為割點(diǎn)割

10、點(diǎn)例例 在下圖中的在下圖中的v3和和v2都都是割點(diǎn)是割點(diǎn), v2, v3,v4,v1, v2, v4,v5都都不不是點(diǎn)割集。是點(diǎn)割集。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e5連通塊劃分：利用dfs求切割點(diǎn)p110g=(v,e)是連通的無(wú)向圖，t是dfs樹，r是它的根結(jié)點(diǎn)，v是非根結(jié)點(diǎn)。根節(jié)點(diǎn)r為切割點(diǎn)，當(dāng)且僅當(dāng)r有多于一個(gè)兒子結(jié)點(diǎn)。非根結(jié)點(diǎn)v為切割點(diǎn)，當(dāng)且僅當(dāng)v的任一兒子結(jié)點(diǎn)w滿足：w不存在它的后裔結(jié)點(diǎn)（包括w）到v的祖先結(jié)點(diǎn)間的后退邊。vw1g1w2g2wsgsvw1g1w2g2wsgs連通塊劃分：利用dfs求切割點(diǎn)p110引進(jìn)low(v)=minnum(w)|w t

11、(v)，其中t(v)是由v出發(fā)沿dfs樹t到達(dá)v的后裔結(jié)點(diǎn)u，最多通過一后退邊(u,w)到達(dá)的點(diǎn)w的集合。利用dfs搜索法對(duì)圖g的全部頂點(diǎn)和邊進(jìn)行檢查過程，沿途留下low(v)的信息。搜索結(jié)束時(shí)，非根結(jié)點(diǎn)v是g的切割點(diǎn)的充要條件是v有兒子w，使得low(w)=num(v)vw1g1w2g2wsgs連通塊劃分：利用dfs求切割點(diǎn)p110(1)i=1, stack=.all v v 作【father(v)=0,mark(v)=0】(2)任選一點(diǎn)r滿足mark(r)=0,作【v=r, mark(v)=1, num(v)=i, low(v)=i 】(3)若所有與v點(diǎn)關(guān)聯(lián)的邊均已給出標(biāo)志，則轉(zhuǎn)(5)；否

12、則任選一未給標(biāo)志的邊(v,w)，給(v,w)邊以v到w的方向，并給以標(biāo)志*表示通過檢查。并將(v,w)邊加到棧stack頂上，轉(zhuǎn)(4)。(4) 若mark(w)=0，則作【i+, low(w)=i , num(w)=i, mark(w)=1, father(w)=v, v=w ，轉(zhuǎn)(3) 】。若mark(w)=1，則作【low(v)=minlow(v), num(w) ，轉(zhuǎn)(3) 】(5)若father(v)!=0，則作 【若low(v)=num(father(v)，則作【從堆棧stack中移走邊(father(v),v)及其上棧中元素并輸出，轉(zhuǎn)(6)】，否則轉(zhuǎn)(6)】； 否則結(jié)束。 (6)l

13、ow(father(v)=minlow(v), low(father(v), v=father(v)， 轉(zhuǎn)(3)。圖的連通性：簡(jiǎn)單有向圖的連通性一個(gè)有向圖一個(gè)有向圖g是強(qiáng)連通的是強(qiáng)連通的充要條件充要條件是是g中有一個(gè)中有一個(gè)回路回路, 它至少它至少包含每個(gè)頂點(diǎn)包含每個(gè)頂點(diǎn)一次。一次。證明證明 充分性充分性 如果如果g中有一個(gè)回路中有一個(gè)回路, 它它至少包含每個(gè)頂點(diǎn)一次至少包含每個(gè)頂點(diǎn)一次, 則則g中中任何兩個(gè)頂點(diǎn)都是相互可達(dá)任何兩個(gè)頂點(diǎn)都是相互可達(dá)的的, 即即g是強(qiáng)連通圖。是強(qiáng)連通圖。必要性必要性 若有向圖若有向圖g是強(qiáng)連通的是強(qiáng)連通的, 則則任何兩個(gè)頂點(diǎn)都是相互任何兩個(gè)頂點(diǎn)都是相互可達(dá)的可達(dá)

14、的, 所以必可作一個(gè)回路經(jīng)過圖中所有各點(diǎn)。所以必可作一個(gè)回路經(jīng)過圖中所有各點(diǎn)。否則必有一個(gè)回路否則必有一個(gè)回路不包含不包含某一頂點(diǎn)某一頂點(diǎn)v, 因而因而v與回路上的各與回路上的各頂點(diǎn)就頂點(diǎn)就不是相互可達(dá)不是相互可達(dá)的的, 與強(qiáng)連通條件矛盾。與強(qiáng)連通條件矛盾。圖的連通性：簡(jiǎn)單有向圖的連通性 在簡(jiǎn)單有向圖在簡(jiǎn)單有向圖g中中,l (1) 若對(duì)若對(duì)g的邊不考慮方向的邊不考慮方向, 即把它看作無(wú)向圖是即把它看作無(wú)向圖是連通的連通的, 則稱則稱g是弱連通是弱連通(weakly connected)的的;l (2) 若對(duì)若對(duì)g中任意兩個(gè)頂點(diǎn)中任意兩個(gè)頂點(diǎn)u和和v, 或者或者u到到v有路有路, 或者或者v到到

15、u有路有路, 則稱則稱g是單向連通的是單向連通的(unilaterally connected);l (3) 若對(duì)若對(duì)g中任意兩個(gè)頂點(diǎn)中任意兩個(gè)頂點(diǎn)u和和v, u到到v有路且有路且v到到u有路有路, 則稱則稱g是強(qiáng)連通的是強(qiáng)連通的(strongly connected)。l 由定義可知由定義可知: 若圖若圖g是強(qiáng)連通的是強(qiáng)連通的, 則必是單向連通則必是單向連通的的; 若圖若圖g是單向連通的是單向連通的, 則必是弱連通的。但這則必是弱連通的。但這兩個(gè)命題兩個(gè)命題, 其逆不成立。其逆不成立。強(qiáng)連通塊的劃分l極大的強(qiáng)連通子圖稱為強(qiáng)連通塊。l強(qiáng)連通塊劃分算法p112-114最短通路問題l求帶權(quán)簡(jiǎn)單連通

16、圖一點(diǎn)到另一點(diǎn)的最短通路dijkstra算法（離散數(shù)學(xué)及其應(yīng)用p477l求一點(diǎn)到其他各點(diǎn)最短通路稍微修改dijkstra算法l求任意兩點(diǎn)間最短距離floyed算法圖的生成樹l圖的生成樹的應(yīng)用道路掃雪ip組播連通簡(jiǎn)單圖的生成樹生成算法：廣度優(yōu)先算法l 任意選取圖中一個(gè)頂點(diǎn)為根。然后添加與這個(gè)頂點(diǎn)相關(guān)聯(lián)的所有邊。在這個(gè)階段所添加的新頂點(diǎn)成為生成樹在1層上的頂點(diǎn)。任意地排序它們。l 下一步，按順序訪問一層上地每個(gè)頂點(diǎn)，只要不產(chǎn)生簡(jiǎn)單回路，就添加與這個(gè)頂點(diǎn)相關(guān)聯(lián)地每條邊到樹里。這樣就產(chǎn)生了樹里在2層上地頂點(diǎn)。l 遵循相同的過程，直到已經(jīng)添加了樹里的所有頂點(diǎn)。l 圖邊數(shù)有窮且連通，故這個(gè)過程以產(chǎn)生生成樹

17、而告終。連通簡(jiǎn)單圖的生成樹生成算法：廣度優(yōu)先算法 例如，對(duì)右圖進(jìn)行廣度優(yōu)先搜索遍歷的過程如圖(c)所示，得到的頂點(diǎn)訪問序列為 v1-v2-v3-v4-v5-v6-v7-v8 v8v5v4v6v7v1v3v2v1v3v6v7v5v2v4v8(c)連通簡(jiǎn)單圖的生成樹生成算法：深度優(yōu)先算法l 任意選取圖中一個(gè)頂點(diǎn)為根。通過相繼地添加邊來(lái)形成在這個(gè)頂點(diǎn)上開始的通路，其中每條新邊都與通路上的最后一個(gè)頂點(diǎn)以及還不在通路上的一個(gè)頂點(diǎn)相關(guān)聯(lián)。繼續(xù)盡可能地添加邊到這條通路。l 若這條通路經(jīng)過圖的所有頂點(diǎn)，則由這條通路組成地樹就是生成樹。否則，則必須添加其他的邊。后退到通路里的次最后頂點(diǎn)，若有可能，則形成在這個(gè)頂

18、點(diǎn)上開始的經(jīng)過還沒有訪問過的頂點(diǎn)的通路。若不能這樣做，則再在通路里后退一個(gè)頂點(diǎn)，然后再試。重復(fù)這個(gè)過程，在所訪問過的最后一個(gè)頂點(diǎn)上開始，在通路上一次后退一個(gè)頂點(diǎn)，只要有可能就形成新的通路，直到不能添加更多的邊為止。l 圖邊數(shù)有窮且連通，故這個(gè)過程以產(chǎn)生生成樹而告終。連通簡(jiǎn)單圖的生成樹生成算法：深度優(yōu)先算法 以下圖(a)中無(wú)向圖為例，深度優(yōu)先搜索遍歷圖的過程如圖(b)所示。 (a) 由此，得到頂點(diǎn)訪問序列為： v1-v2-v4-v8-v5-v3-v6-v7 (b)v8v5v4v6v7v1v3v2v5v8v7v6v4v3v2v1連通簡(jiǎn)單圖的生成樹生成算法：深度優(yōu)先算法l如何生成所有的生成樹？（決策

19、樹）l本質(zhì)：回溯連通簡(jiǎn)單圖的生成樹生成算法：深度優(yōu)先算法l回溯應(yīng)用舉例1、圖著色能否用3種顏色為右圖著色，使得相鄰頂點(diǎn)不同顏色？2、n皇后問題 在n*n棋盤上，如何放置n個(gè)皇后，使得沒有兩個(gè)皇后可以互相攻擊？（p102）連通簡(jiǎn)單圖的生成樹生成算法：深度優(yōu)先算法l回溯應(yīng)用舉例3、迷宮：求出在下面的迷宮里從標(biāo)記x的出發(fā)位置到出口的通路1、圖著色 首先選擇某個(gè)頂點(diǎn)a并且指定它的顏色為1，然后挑選第二個(gè)頂點(diǎn)b，而且若b不與a相鄰，則指定它的顏色為1。否則，指定b顏色為2。然后來(lái)到第三個(gè)頂點(diǎn)c。若有可能，則對(duì)c用顏色1。否則，若有可能則用顏色2。只有當(dāng)顏色1和顏色2都不能用時(shí)才應(yīng)當(dāng)用顏色3。 繼續(xù)這個(gè)過

20、程，只要有可能就指定n種顏色表中第一種允許的顏色給新頂點(diǎn)。若遇到不能用n種顏色中的任何一種來(lái)著色，則回溯到最后一次所做的指定，并且若有可能就改變最后著色的頂點(diǎn)的顏色，用顏色表中下一種允許的顏色。若不可能改變顏色，則再回溯到更前面的指定，一次后退一步，知道有可能改變一個(gè)頂點(diǎn)的顏色為止。然后只要有可能就繼續(xù)指定新頂點(diǎn)的顏色。圖著色能否用3種顏色為右圖著色，使得相鄰頂點(diǎn)不同顏色？2、n皇后問題l 從空棋盤開始，在k+1階段上，嘗試在棋盤上第k+1行里放置一個(gè)新的皇后，其中前k行里已經(jīng)有了皇后。檢查第k+1行里的格子，從第一列的格子開始，尋找放置這個(gè)皇后的位置，使得它不與已經(jīng)在棋盤上的皇后在同一行里或

21、在同一斜線上。l 若不可能在第k+1行里找到放置皇后的位置，則回溯到第k行里對(duì)皇后的放置。在這一行里下一個(gè)允許的列里放置皇后，若這樣的行存在的話。若沒有這樣的列存在，則繼續(xù)回溯。2、n皇后問題l可以把這個(gè)問題可能結(jié)果看成一個(gè)1，2，3，4的排列，如（1，4，3，2）表示第一行的第1列，第二行的第4列，第三行的第3列，第四行的第2列放置皇后。l可以將所有可能的排列用n元n層的搜索樹表示。l對(duì)該樹做深度優(yōu)先搜索，并在每一步檢查是否符合要求，不滿足則回溯。任何一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑都是問題的解3、迷宮每一步的可能行動(dòng)序列為1向左，2向上，3向右，4向下。每一步如果可能盡量按照行動(dòng)序列次序執(zhí)行。

22、遇到走不通的時(shí)候看看是否有下個(gè)行動(dòng)可執(zhí)行。如果沒有則回溯上一步，換用行動(dòng)序列中的下個(gè)行動(dòng)。連通簡(jiǎn)單圖的生成樹生成算法：其他算法l教材p95：利用det(bkbkt)生成樹的清單l教材p96：利用基本割集多項(xiàng)式生成l教材p98：minty算法l教材p101：mayeda-seshu算法最小生成樹 問題背景： 假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要n-1條線路。這時(shí)，自然會(huì)考慮這樣一個(gè)問題，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通信網(wǎng)。 在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價(jià)。n個(gè)城市之間，最多可能設(shè)置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n

23、-1條，以使總的耗費(fèi)最少呢? 最小生成樹分析問題（建立模型）： 可以用連通圖來(lái)表示n個(gè)城市以及n個(gè)城市間可能設(shè)置的通信線路，其中圖的頂點(diǎn)表示城市，邊表示兩城市之間的線路，賦于邊的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個(gè)通信網(wǎng)?，F(xiàn)在，我們要選擇這樣一棵生成樹，也就是使總的耗費(fèi)最少。這個(gè)問題就是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(minimumcostspanningtree)(簡(jiǎn)稱為最小生成樹)的問題。一棵生成樹的代價(jià)就是樹上各邊的代價(jià)之和。最小生成樹 構(gòu)造最小生成樹可以有多種算法。其中多數(shù)算法利用了最小生成樹的下列一種簡(jiǎn)稱為mst的性質(zhì)： 假設(shè)g=(v

24、，e)是一個(gè)連通圖，u是頂點(diǎn)集v的一個(gè)非空子集。若 (u，v)是一條具有最小權(quán)值(代價(jià))的邊，其中u u，vv-u，則必存在一棵包含邊 (u，v)的最小生成樹。最小生成樹 可以用反證法證明之： 假設(shè)圖g的任何一棵最小生成樹都不包含(u ,v)。設(shè)t是連通網(wǎng)上的一棵最小生成樹，當(dāng)將邊(u，v)加入到t中時(shí)，由生成樹的定義，t中必存在一條包含(u,v)的回路。另一方面，由于t是生成樹，則在t上必存在另一條邊(u,v)，其中uu，vv-u，且u和u之間，v和v之間均有路徑相通。刪去邊(u, v)，便可消除上述回路，同時(shí)得到另一棵生成樹t，。因?yàn)?u，v)的代價(jià)不高于(u，v)，則t的代價(jià)亦不高于t，t是包含(u，v)的一棵最小生成樹。由此和假設(shè)矛盾。uvuvuv-u最小生成樹算法 解決方案： 普里姆(prim)算法和克魯斯卡爾(kruskal)算法是兩個(gè)利用mst性質(zhì)構(gòu)造最小生成樹的算法。 下面先介紹prim算法。 假設(shè)g=(v，e)是連通圖，te是n上最小生成樹中邊的集合。算法從u=u0(u0v)，te=開始，重復(fù)執(zhí)行下述操作：在所有uu，v v-u的邊(u，v) e中找一條代價(jià)最小的邊(u0 ，v