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

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

隨筆 - 0
文章 - 10
評(píng)論 - 5
引用 - 0

最小生成樹之Kruskal算法

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

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

我們先來介紹Kruskal算法，Prim算法請(qǐng)參閱最小生成樹之Prim算法

該算法的基本思路：貪心，如何貪心呢？
它的貪心準(zhǔn)則是：
1.每次從剩下的邊中選擇一個(gè)不會(huì)產(chǎn)生環(huán)路而且權(quán)值最小的邊加入到已經(jīng)選擇好的邊的集合中。
2.它需要e步的操作，e表示圖的邊數(shù)，我們可以按權(quán)值排好序后，對(duì)每一條邊進(jìn)行選擇，如果加入到已經(jīng)選擇好的邊中會(huì)產(chǎn)生回路的現(xiàn)象，就不要了。。。否則加入到已經(jīng)選擇好的邊中。
3.我們還需用到并查集的思想，有關(guān)并查集的介紹，請(qǐng)查看我的另一篇博文不相交集合數(shù)據(jù)結(jié)構(gòu)
4.復(fù)雜度：O(ElgE)，其中E為圖的邊數(shù)

接下來我們引用POJ上的一個(gè)經(jīng)典題目來分析，題目網(wǎng)址http://acm.pku.edu.cn/JudgeOnline/problem?id=1861

題目大意是：題目給出的是圖的頂點(diǎn)和所有邊的集合，要求輸出的是最小生成樹的邊

我們來看下源碼啦：

#include<iostream>

using namespace std;

#include<algorithm>

#include <memory.h>

#define MAXEDGE 15001//最大邊數(shù)

#define MAXNODE 1001 //最大節(jié)點(diǎn)數(shù)

int p[MAXNODE],rank[MAXNODE];//用于不相交集合

int start[MAXEDGE],end[MAXEDGE],weight[MAXEDGE],VNum,ENum;//分別為邊的起點(diǎn)，終點(diǎn)，權(quán)重，節(jié)點(diǎn)數(shù)和邊數(shù)

int result_s[MAXEDGE],result_e[MAXEDGE];//分別為存儲(chǔ)最小生成樹的起點(diǎn)，終點(diǎn)

int max_weight,id[MAXEDGE];

void make_set(int x)

{

p[x]=x;

rank[x]=0;

}

int find_set(int x)

{

if(p[x]!=x)

p[x]=find_set(p[x]);

return p[x];

}

void Union(int x,int y)

{

x=find_set(x);

y=find_set(y);

if(rank[x]>rank[y])

p[y]=x;

else if(rank[x]<rank[y])

p[x]=y;

else if(rank[x]==rank[y])

{

p[x]=y;

rank[y]++;

}

bool cmp(int i,int j)//用于sort函數(shù)

{

return weight[i]<weight[j];

}

void Kruskal()

{

int i,min,index=0,count=0,k=0;

max_weight=0;

for(i=1;i<=VNum;i++)

make_set(i);

sort(id,id+ENum,cmp);//對(duì)所有邊進(jìn)行排序，注意id數(shù)組的妙用

while(true){

min=id[index++];

if(find_set(start[min])!=find_set(end[min])){ //對(duì)每條邊進(jìn)行處理，如果起點(diǎn)和終點(diǎn)不在同一集合合并之

Union(start[min],end[min]);

result_s[k]=start[min];//保存結(jié)果

result_e[k++]=end[min];

count++;

if(max_weight<weight[min])

max_weight=weight[min];

}

if(count==VNum-1) break;//當(dāng)邊數(shù)等于節(jié)點(diǎn)數(shù)-1的時(shí)候表示已經(jīng)完成

}

int main()

{

int i;

cin>>VNum>>ENum;

for(i=0;i<ENum;i++){

cin>>start[i]>>end[i]>>weight[i];

id[i]=i;

}

Kruskal();

cout<<max_weight<<endl<<VNum-1<<endl;

for(i=0;i<VNum-1;i++)

cout<<result_s[i]<<" "<<result_e[i]<<endl;

return 0;

}

posted on 2009-09-13 21:18 原語餓狼閱讀(712) 評(píng)論(0) 編輯收藏引用所屬分類: 圖論

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


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

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

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