yuanyuelang

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

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

最小生成樹之Kruskal算法

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

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

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

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

接下來我們引用POJ上的一個經典題目來分析，題目網址http://acm.pku.edu.cn/JudgeOnline/problem?id=1861

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

我們來看下源碼啦：

#include<iostream>

using namespace std;

#include<algorithm>

#include <memory.h>

#define MAXEDGE 15001//最大邊數

#define MAXNODE 1001 //最大節點數

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

int start[MAXEDGE],end[MAXEDGE],weight[MAXEDGE],VNum,ENum;//分別為邊的起點，終點，權重，節點數和邊數

int result_s[MAXEDGE],result_e[MAXEDGE];//分別為存儲最小生成樹的起點，終點

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函數

{

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);//對所有邊進行排序，注意id數組的妙用

while(true){

min=id[index++];

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

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

result_s[k]=start[min];//保存結果

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

count++;

if(max_weight<weight[min])

max_weight=weight[min];

}

if(count==VNum-1) break;//當邊數等于節點數-1的時候表示已經完成

}

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) 評論(0) 編輯收藏引用所屬分類: 圖論

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


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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