Prim算法求解過(guò)程

T1T1法求解過(guò)程一、算用途：從某給定點(diǎn)開(kāi)始，求解無(wú)向連通加權(quán)圖W)的最小生成樹(shù)T=(VW).TTT二、算步驟：設(shè)W)是無(wú)相連通加權(quán)圖，|V|=n,要從v1點(diǎn)始求解）1令已經(jīng)落在樹(shù)中的點(diǎn)集V={v},=Φ,尚未落在樹(shù)T上的點(diǎn)集～V；TTTT2.找集合V與～V之間的權(quán)最小的邊T

中∈VvVijiTjT令V{v},V:=～V-{v},E:=E∪{e}；TTjTTjTT3.當(dāng)V=V,TWT三、例

V=時(shí)，算法中止，即得到原圖G的一棵最小生成樹(shù)，再計(jì)算v

2

7

v

4v

1

14

2v3

51

3v5

26

v

6

求圖的最小生成樹(shù)。（從點(diǎn)開(kāi)始圖1[解]解法過(guò)一：示法。①②

v1V={v},V=V-V={v,…v}.T1TT231

v

2vV={v},～V={v…v}.T1T36

③

v

212v

1

v

3V={v,v},～V={v,v}T23T46④

1

v

2v

1

2

1v

3

v

5V={v,vv},～V={v,v}T23T46⑤

v

2

v

41v

1

2

21v

3

v

5V={v,vv,v},～={v}T23eq\o\ac(○,6)

v

2

v

41

2v

1

23

v

6v

3

1

v

5V={v,vv,vv}=V,～V=算法中止。T23T所以，T如上圖所示且WT

解法過(guò)二：列表法步驟

VT

～VT

V與～VTT之間的最短邊

最短邊的權(quán)

樹(shù)權(quán)1vv,v,v134562v,vv,v133v,vv,v,v14564v,v,vv,v1465v,v,vv166v,v,v,vΦ16最終得到的最小生成樹(shù)T如下圖所示，W=9.T

(v)12(v)23(v)35(v)54(v)46-----

1123143729-----------v

2

v

41

2v

1

231

v

6v

3

v

5（注：做此類(lèi)題目時(shí)請(qǐng)選取上述兩種過(guò)程中的一種規(guī)范書(shū)寫(xiě)四、思題：1.此算法的最終結(jié)果與起始點(diǎn)的選取有沒(méi)有關(guān)系？2.起始點(diǎn)相同的情況下，最后結(jié)果（最小生成樹(shù)和）會(huì)不會(huì)不同？T（試從v開(kāi)始求圖最小生成樹(shù)）13.算法中每一步加邊時(shí)是否需要考慮避免與已經(jīng)在中的邊回路？為什么？4.此算法每一步都是選V與～V兩點(diǎn)集之間的TT

,v),vV,vV）ijiTjT中權(quán)最小的邊，而不是這一步新加入V的點(diǎn)的鄰邊中權(quán)最小的，否則得到的不是最T小生成樹(shù)（例如圖2v

21

23

v

2

2

v

2

15

31v

2

4

v

2

1616圖2五、Kruskal算法與算法的區(qū)別：求最小生成樹(shù)的算法Kruskal算法

起始步驟最小權(quán)的邊（求解者自行選取）

算法過(guò)程通過(guò)每一步選取最短邊來(lái)找到最小生成樹(shù)

適合范圍稀疏圖

時(shí)間復(fù)雜度O(mlogm),是的邊數(shù)每一步通過(guò)選Prim算法

規(guī)定了算法的起始點(diǎn)

取點(diǎn)集V和T～V之間的最T短邊來(lái)進(jìn)一步

稠密圖

O(n

2

)更新這兩個(gè)點(diǎn)集D氏算法解程[例題]試求無(wú)賦權(quán)中v到v的最短路。v

2

7

v

4v

1

14

2v3

51

v

35

26

v6解：D氏法的具體步驟如表所示：步永久號(hào)點(diǎn)集P

最近距離點(diǎn)

最短距離

D(v2

D(v)3

D(v4

D(v5

D(v61v

1

v

2

1

1

4

∞

∞

∞2v,v123v,vv12,34v,vvv12,3,55v,vvvv12,3,5,4

vvvv

3546

3479

1*1*1*1*

33*3*3*

8877*

644*4*

∞∞1096

v,vvvv,12,3,5,4v6

------

------

1*

3*

7*

4*

9*從而，的P標(biāo)號(hào)為，到v的短距離9.616

注：“短距離”表示在當(dāng)前集合T中最短距離；“最近距離點(diǎn)”為其相應(yīng)的結(jié)點(diǎn)。D(v表示各結(jié)點(diǎn)當(dāng)前的標(biāo)號(hào)i*表新加入集合P中點(diǎn)。作、測(cè)驗(yàn)題中若有求解最短路徑問(wèn)題時(shí)，請(qǐng)畫(huà)出此表格表明求解過(guò)程。思考題：最完成此表后，如何找到從出到某點(diǎn)的最短路徑？1i若算法過(guò)程中某一步出現(xiàn)了兩個(gè)相等的最短距離值時(shí)，選取哪一個(gè)加入集合P？提示：從以下兩類(lèi)問(wèn)題考慮：(1)求v1出發(fā)到某點(diǎn)的最短距離；(2)求v1出發(fā)到其它各點(diǎn)的最短距離。Kruskal算法（避圈）求解過(guò)程一、算用途：求解無(wú)向連通加權(quán)圖E,W)的最小生成樹(shù)T=(VEW).TTT二、算步驟：設(shè)G=(V,E,W)是無(wú)相連通加權(quán)圖，|V|=n,|E|=m。不妨設(shè)G中沒(méi)有環(huán)，否則把所有的環(huán)先去掉。1按照邊權(quán)從小到大的關(guān)系，將m條邊排序：

e,e,e;122.取e∈E，然后依次檢查e,,…,若(j≥2)與已經(jīng)在T中的邊1T23mj不構(gòu)成回路，則取e∈E，否則就舍棄；jTj3.當(dāng)V=V（或|=n-1，或加入任何一條邊都產(chǎn)生回路）時(shí)，算法中止，即得到原TT圖的一棵最小生成樹(shù)，再計(jì)算W。T三、題2

v

47v

1

1

2

5

3

2

v

6

求此無(wú)向連通加權(quán)圖的最小生成樹(shù)。4

v

3

1

v

5

6[解]對(duì)圖中各邊的權(quán)進(jìn)行從小到大排序：e=(v,v),e=(v),e=(v),e=(v),=(v,v),e=(v,ve=(v),e=(v,v)11223423455613e=(v,v)924

TT則由Kruskal算法，最小生成樹(shù)的邊集合的序列為：①

1

v

2v

1②

v

21v

1

1v

3

v

5③

1

v

22v

1

v

3

1

v

5④

1

v

2

v

4

2v

1

v

3

2

1

v

5

v

6⑤

v

2

v

41

2v