關于圖的prime和kruskal算法

作者原創，轉載請留言告知！！！

關于圖的prim和kruskal算法

• 圖
• • prim算法
  • kruskal 算法
• 下面我将通過POJ的題來對這兩個算法進行解析
• • • [POJ2485](http://poj.org/problem?id=2485)
• 何謂并查集？

圖

詳情介紹請見我的部落格：圖

prim算法

一般來說，prim算法常用于網比較稠密的圖。

對于一個點來說，找到權重最小的連接配接點。之後對于這兩個點來說，找到這兩個點中權重最小的另外一個點（即沒有經過周遊的點）。之後以此類推，直到周遊完成。

可以把prim算法了解為點優先。

kruskal 算法

kauskal适用于網比較稀疏的圖

先對權重由小到大排序，依次周遊權重兩邊的點，如果點已經被周遊過，則跳過這個權重，繼續周遊。直到周遊完成。

可以把kruskal算法了解為邊優先。

1. 對于是否周遊過 ，我在圖的部落格中已經說過，可以建立一個數組，用1或0來表示是否周遊成功；
2. 對于鄰接連結清單來說，可以把權重放到連結清單裡面；

下面我将通過POJ的題來對這兩個算法進行解析

POJ2485

• prim 算法

//POJ 2485高速公路 
//這裡用的是鄰接矩陣下的圖的prime算法，即基于貪心思想的深搜周遊     
#include<stdio.h>
#define M 502
int main(void)
{
	long flag=-1,min=65537,arcs[M][M];
	int i,j,n,P=0,num,visited[M],PtT[M];//最後一個用空間換時間 
	scanf("%d",&n);
	for(int k=0;k<n;k++){
		flag=-1;P=0;		//注意第二組資料時的初始化 
		scanf("%d",&num);
		for(i=0;i<num;i++){
			for(j=0;j<num;j++)
				scanf("%d",&(arcs[i][j]));		//标準輸入 
			visited[i]=0;						//初始化 
		}//for
		i=0;
		while(P<num-1){
			if(visited[i]==0){
				visited[i]=1;
				PtT[P++]=i;
				for(int temp=0;temp<P;temp++)	//PtT用來記錄i 
					for(j=0;j<num;j++)
						if(min>arcs[PtT[temp]][j]&&arcs[PtT[temp]][j]!=0&&visited[j]==0){		//已經周遊過的所有樹的子樹中權重最小且沒有被周遊過的 
							min=arcs[PtT[temp]][j];
							i=j;		//之前是把這個等式放到外面，就不确定j是否為0
						}
				flag<min?flag=min:flag=flag; 
				min=65537;
			}//if
		}//while
		printf("%d\n",flag);  //注意加回車 
	}//for
	return 0;
}

           

• kruskal算法

//POJ 2458 高速公路
//用鄰接矩陣的kruskal算法 并查集
//頭檔案和排序函數請自己補充
#define MAX 502
struct LINE{
	int weight;//弧的權重
	int mmp,mvp;//弧的兩個節點
}node[MAX];
int coun=0,pre[MAX],sun=0;
int Find(int n) {
	while(n!=pre[n])
		n=pre[n];
	return n;
}//尋找祖宗節點
void Merge_set(LINE node) {
	int i=Find(node.mmp);
	int j=Find(node.mvp);
	if(i!=j) {
		pre[i]=j;
		coun++;	//記錄路數
		sun+=node.weight;
	}
}//這條弧入集
int main() {
	int n,num;
	int temp=0;
	scanf("%d",&n);
	for(int k=0; k<n; k++) {
		scanf("%d",&num);
		for(int i=1; i<num*num/2; i++)
			pre[i]=i;//此時并查集都是獨立的
		for(int i=1; i<=num; i++)
			for(int j=1; j<=i; j++) {	//倒三角輸入
				scanf("%d",&node[temp].weight);
				node[temp].mmp=i;
				node[temp].mvp=j;
				temp++;
			}
		sort(k,k+num*num/2,comp);
		for(int i=0; i<num*num; i++)
			Merge_set(node[i]);
		coun=0;
		sun=0;
		printf("%d",sun);
	}
	return 0;
}
           

這裡講到了并查集的概念，那麼

何謂并查集？

并查集是一個包含特定數值的集合。我們不能像prime算法那樣用一個visit數組來标記是否周遊，因為prim是點優先而kruskal是邊優先。看下圖：

如上所示，第一步是連結A和B，第二步是連結D和C，如果按照此時把每個點都标記的話，很顯然，在B和C沒連到一塊的時候4個點就已經标記完成了。

故此時需要 知道他們這些點是不是已經連到一塊了。很顯然，如果每次用深搜或者廣搜來檢查的話有很麻煩，此時并查集就應運而生。

判斷是否在一個并查集的标準就是祖宗是否一樣。祖宗可以了解為幾個相連點之間的任意一個點，為了容易判斷，就會把祖宗設為一條線中開始的那個點，譬如上圖，就可以設A為祖宗。請想一想，如果每個點有相同的祖宗，不就證明了他們在同一條線上，也就是說在同一個并查集中。

剛開始時，每個點都是一個不同的并查集，因為他們互不相連。每加入一個點的時候，就要通過find函數找出它的祖宗，如果祖宗不同，就把他們的祖宗設為一個，即歸到一個并查集當中去。

int Find(int n) {
	while(n!=pre[n])
		n=pre[n];
	return n;
}//尋找祖宗節點
void Merge_set(LINE node) {
	int i=Find(node.mmp);
	int j=Find(node.mvp);
	if(i!=j) {
		pre[i]=j;
		coun++;	//記錄路數
		sun+=node.weight;
	}
}//這條弧入集
           

那麼，

就到這裡了！