yuanyuelang

導(dǎo)航

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計

隨筆 - 0
文章 - 10
評論 - 5
引用 - 0

最小生成樹之Prim算法

最小生成樹是圖論的一個重要部分，解決這個問題的算法主要有Kruskal算法和Prim算法。

最小生成樹:顧名思義是一棵樹，該樹是圖中權(quán)值和最小的。

這篇文章介紹Prim算法，Kruskal算法請參閱最小生成樹之Kruskal算法。

Prim算法的主要思路：
1.圖G={V,E},V表示節(jié)點集，E表示邊集，初始時將V0從V中拿出，放入空集合U中，U={V0}，T(E)空
2.選擇和集合U有連接的且最近的點Vx（在V中），放入U，U={V0,Vx},并將邊加入到T(E)中。
3.重復(fù)第二步，直到U=V
很明顯需要n-1步，n為圖的節(jié)點數(shù)。

現(xiàn)在我們就是要如何把它變成代碼的問題了。
1.存儲問題，我們需要一個二元數(shù)組graph下標(biāo)存放節(jié)點，數(shù)組值存放權(quán)值。比如(1,2)有邊，權(quán)值為3，則graph[1][2]=3,同時graph[2][1]=3，沒有邊的點用INF（無窮大）表示咯。
2.如何判斷和最近的點，由于每一次進(jìn)來都會改變情況，所以每次都要更新，我們用一個一元數(shù)組opt[n]來表示，數(shù)組下標(biāo)表示節(jié)點號，值表示該節(jié)點到U的最短距離。記住，加入到U集合的點是不用再管它的了，所以，我們還要設(shè)置一個數(shù)組flag[n]，來設(shè)置標(biāo)志位，看是否已經(jīng)加入到U集合了。
3.這樣的話大功也就告成了，一般就會寫了吧。如果要保存各個邊的話，還要添加一個數(shù)組line[n]來表示節(jié)點到U的最短距離到底是連接U中哪一個節(jié)點的。

看看代碼，分析分析吧。。記住很重要的，自己舉個例子看看。最后一定要熟練掌握其原理，并且快速的寫出代碼。

#define MAXN 100

#define INF 0xfffffff

int result_s[MAXN],result_e[MAXN];//保存邊

void prim(int graph[MAXN][MAXN],int opt[],int n)

{

int i,j,min,vertex，line[n];

bool flag[n];

for(i=0;i<n;i++){ //初始化

opt[i]=graph[0][i];

line[i]=0;

flag[i]=false;

}

flag[0]=true;

for(i=1;i<n;i++){

min=INF;

for(j=1;j<n;j++){

if(!flag[j]&&opt[j]<min){//選擇最優(yōu)點

min=opt[j];

vertex=j;

}

flag[vertex]=true; //加入到U集合

result_s[i]=line[vertex];//保存

result_e[i]=vertex;

for(j=1;j<n;j++){//更新

if(!flag[j]&&graph[vertex][j]<opt[j])

opt[j]=graph[vertex][j];

line[j]=vertex;

}

因為代碼是自己當(dāng)場寫出來，寫出來和原來正確代碼相比較了，如果讀者發(fā)現(xiàn)有錯，還望指正。
我想我們就是要鍛煉這種寫代碼的能力，不能太依靠模板，不然忘得快。
注意：最后結(jié)果都知道了，opt[]保存的是最小生成樹的選入的各個邊的權(quán)值，result_s[]和result_e保存了到底是哪些點組成的最小生成樹。

posted on 2009-09-14 18:47 原語餓狼閱讀(533) 評論(0) 編輯收藏引用所屬分類: 圖論

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: 每對頂點間的最短路徑之Floyd-Warshall算法單源最短路徑之Dijkstra算法最小生成樹之Prim算法最小生成樹之Kruskal算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品