數(shù)學(xué)實(shí)驗(yàn)課件 第13章13.2

13.2最小生成樹(shù)的算法求解最小生成樹(shù)有Kruskal算法和Prim算法．1Kruskal算法描述如下：

對(duì)于一個(gè)連通的賦權(quán)圖G，按照如下步驟構(gòu)造其最小生成樹(shù)T：1）找出G所有邊中的權(quán)重最小的邊e1作為T的第一條邊；2）選擇

，使得e2的權(quán)重最??；3）選擇

，使得e3的權(quán)重最小，且不能和前面所選的邊構(gòu)成圈；4）重復(fù)步驟3），直到找出n-1條邊，則得到G的最小生成樹(shù)．

此算法可以稱為“加邊法”，初始最小生成樹(shù)邊數(shù)為0，每迭代一次就選擇一條滿足條件的最小代價(jià)邊，加入到最小生成樹(shù)的邊集合里．例13.3用Kruskal算法求圖13-3所示的最小生成樹(shù)．解（1）邊v3v4的權(quán)重為所有邊中最小的，選取v3v4∈E作為第一條邊，即e1=v3v4；

（2）邊v1v4的權(quán)重為剩下的邊中最小的，選取v1v4∈E-{e1}作為第二條邊，即e2=v1v4；

（3）邊v1v2的權(quán)重為剩下的邊中最小的，但是加進(jìn)來(lái)后會(huì)構(gòu)成圈，故在E-{e1,e2,v1v2}中選取權(quán)重最小的邊v1v3作為第三條邊，即e3=v1v3；

（4）找到了3條邊，停止．

利用Kruskal算法得到最小生成樹(shù)見(jiàn)圖13-4，得到的最小生成樹(shù)的權(quán)重是15．圖13-4Kruskal算法得到最小生成樹(shù)2Prim算法

對(duì)于連通的賦權(quán)圖

，設(shè)置兩個(gè)集合P和Q，其中P用于存放G的最小生成樹(shù)中的頂點(diǎn)，集合Q存放G的最小生成樹(shù)的邊．

1）初始化頂點(diǎn)集P={v1}，v1∈V，邊集Q=?；

2）選擇v2∈V-P使得邊v1v2的賦權(quán)最小，P={v1,v2},Q={v1v2}；

3）重復(fù)步驟2），知道P=V，停止．

此算法可以稱為“加點(diǎn)法”，每次迭代選擇代價(jià)最小的邊對(duì)應(yīng)的點(diǎn)，加入到最小生成樹(shù)中.算法從某一個(gè)頂點(diǎn)s開(kāi)始，逐漸長(zhǎng)大覆蓋整個(gè)連通網(wǎng)的所有頂點(diǎn)．例13.4用Prim算法求圖13-3所示的最小生成樹(shù).解（1）初始化頂點(diǎn)集P={v1}，v1∈V，邊集Q=?；

（2）與v1相連的邊v1v2，v1v3，v1v4中權(quán)重最小的是v1v4，故選擇v4，P={v1,v4},Q={V1,V4}；

（3）選擇v2∈V-P，使得在與P中點(diǎn)相連的邊中v2v4的權(quán)重是最小的，P={v1,v4,v2},Q={v1v4,v2v4}（4）選擇v3∈V-P，使得在與P中點(diǎn)相連的邊中v1v3的權(quán)重是最小的，P={v1,v4,v2,v3},Q={v1v4,v2v4,v1v3}；

（5）