程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 數據結構（C實現）------- 最小生成樹之Kruskal算法

數據結構（C實現）------- 最小生成樹之Kruskal算法

編輯：關於C語言

數據結構（C實現）------- 最小生成樹之Kruskal算法

算法描述：

Kruskal算法是按權值遞增的次序來構造最小生成樹的方法。

　　　假設G(V,E)最一個具有n個頂點的連通網，頂點集V={v1,v2,....,vn}。設所求的最小生成樹為T={U,TE},其中U是T的頂點集，TE是Ｔ的邊集，U和TE的初始值為空集。Kruskal算法的基本思想如下：將最小生成樹初始化為T=(V,TE),僅包含 G的全部頂點，不包含G的任一條邊，此時，T由n 個連通分量組成，每個分量只有一個頂點；將圖中G中的邊按權值從小到大排序，選擇代價最小了一條邊，若該邊所依附的頂點分屬於T中的不同的連通分量，則將此邊加入到TE中，否則，捨棄此邊而選擇下一條代價最小的邊。依次類推，直至TE中包含n-1條邊（即T中所有的頂點都在同一連通分量上）為止。

算法實現：

　　　設置一個edge數組存儲連通網中所有的邊，為了便於選擇當前權值最小的邊，需要將edge中的邊按權值從小到大進行排列。

　　　而在連通分量的合並上，可以采用集合的合並方法，對於有n個頂點的連通網，設置一個數組father[0...n-1]，其初始值為-1,表示n個頂點在不同的連通分量上。然後，依次掃描edge數組中的每一條邊，並查找相關聯的兩個頂點所屬的連通分量，假設vf1和vf2為兩個頂點的所在樹的根節點的序號，若vf1不等於vf2，則表明這條邊的兩個頂點不屬於同一個連通分量，則將這條邊作為最小生成樹的邊並輸出，然後合並它們所屬的兩個連通分量。

算法代碼：

int findFather(int father[],int v){
	int t = v;
	while(father[t] != -1)
		t = father[t];
	return t;
}



/* *
 *Kruskal算法求最小生成樹
 * */ 
void Kruskal_MG(MGraph MG,Edge edge[]){
	int father[MAX_VEX_NUM];
	int i,count,vf1,vf2;
	// 初始化father數組
	for(i = 0;i < MAX_VEX_NUM;i++){
		father[i] = -1;
	}
	i = 0;
	count = 0; // 統計加入最小生樹中的邊數
	// 遍歷任意兩個結點之間的邊
	while(i < MG.arcnum && count < MG.arcnum){
		vf1 = findFather(father,edge[i].start);
		vf2 = findFather(father,edge[i].end);
		// 如果這兩個節點不屬於同一個連通分量，則加入同一個連通分量
		if (vf1 != vf2){
			father[vf2] = vf1;
			count++;
			printf(%c,%c,%d
,MG.vexs[edge[i].start],MG.vexs[edge[i].end],edge[i].cost);
		}
		i++;
	}
}

　　　其中，函數findFather的作用就是找指定節點所屬的連通分量，在這裡也就是找其所在樹的根節點在數組中的序號。

算法說明：

　　　對於帶權圖G中e條邊的權值的排序方法可以有多種，這裡采用的是最簡單的冒泡排序法，時間復雜度為O(n^2)。而判斷新選擇的邊的兩個頂點是否在同一個連通分量中，這個問題等價於一個在最多有n 個頂點的生成樹中遍歷尋找新選擇的邊的兩個節點是否存在的問題，所以此算法的復雜度最壞情況下是O(n^2)。

　　　注意：一般來講，Prim算法的時間復雜度為O(n^2),因此適合於稠密圖，而Kruskal算法需要對e條邊進行排序，最快的情況下復雜度為O(elog2e)，因此對於稀疏圖，采用Kruskal算法比較合適。

完整代碼：

/*
 * =====================================================================================
 *
 *       Filename:  Kruskal.c
 *
 *    Description:  最小生成樹之Kruskal算法
 *
 *        Version:  1.0
 *        Created:  2015年05月06日 21時25分12秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  jesson20121020 (), [email protected]
 *   Organization:  
 *
 * =====================================================================================
 */


#include 
#include 
#define MAX_VEX_NUM 50
#define MAX_ARC_NUM 100
#define UN_REACH 1000




typedef char VertexType;
typedef enum {
	DG, UDG
} GraphType;
typedef struct {
	VertexType vexs[MAX_VEX_NUM];
	int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
	int vexnum, arcnum;
	GraphType type;
} MGraph;



/**
 * 根據名稱得到指定頂點在頂點集合中的下標
 * vex  頂點
 * return 如果找到，則返回下標，否則，返回０
 */
int getIndexOfVexs(char vex, MGraph *MG) {
	int i;
	for (i = 1; i <= MG->vexnum; i++) {
		if (MG->vexs[i] == vex) {
			return i;
		}
	}
	return 0;
}

/**
 * 創建鄰接矩陣
 */
void create_MG(MGraph *MG) {
	int i, j, k,weight;
	int v1, v2, type;
	char c1, c2;
	printf(Please input graph type DG(0) or UDG(1) :);
	scanf(%d, &type);
	if (type == 0)
		MG->type = DG;
	else if (type == 1)
		MG->type = UDG;
	else {
		printf(Please input correct graph type DG(0) or UDG(1)!);
		return;
	}

	printf(Please input vexmun : );
	scanf(%d, &MG->vexnum);
	printf(Please input arcnum : );
	scanf(%d, &MG->arcnum);
	getchar();
	for (i = 1; i <= MG->vexnum; i++) {
		printf(Please input %dth vex(char):, i);
		scanf(%c, &MG->vexs[i]);
		getchar();
	}

	//初始化鄰接矩陣
	for (i = 1; i <= MG->vexnum; i++) {
		for (j = 1; j <= MG->vexnum; j++) {
			if(i == j)
				MG->arcs[i][j] = 0;
			else
				MG->arcs[i][j] = UN_REACH;
		}
	}

	//輸入邊的信息，建立鄰接矩陣
	for (k = 1; k <= MG->arcnum; k++) {
		printf(Please input %dth arc v1(char) v2(char) weight(int): , k);

		scanf(%c %c %d, &c1, &c2,&weight);
		v1 = getIndexOfVexs(c1, MG);
		v2 = getIndexOfVexs(c2, MG);
		if (MG->type == 1)
			MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight;
		else
			MG->arcs[v1][v2] = weight;
		getchar();
	}




}
/**
 * 打印鄰接矩陣和頂點信息
 */
void print_MG(MGraph MG) {
	int i, j;
	if(MG.type == DG){
		printf(Graph type: Direct graph
);
	}
	else{
		printf(Graph type: Undirect graph
);
	}

	printf(Graph vertex number: %d
,MG.vexnum);
	printf(Graph arc number: %d
,MG.arcnum);

	printf(Vertex set:
 );
	for (i = 1; i <= MG.vexnum; i++)
		printf(%c	, MG.vexs[i]);
	printf(
Adjacency Matrix:
);

	for (i = 1; i <= MG.vexnum; i++) {
		j = 1;
		for (; j < MG.vexnum; j++) {
			printf(%d	, MG.arcs[i][j]);
		}
		printf(%d
, MG.arcs[i][j]);
	}
}


// 定義邊結構體
typedef struct{
	int start;
	int end;
	int cost;
}Edge;


/* *
 * 由鄰接矩陣得到邊的信息
 *
 * */
void init_edge(MGraph MG,Edge edge[]){
	int i,j;
	int count = 0;
	if(MG.type == 0){
		for(i = 1; i <= MG.vexnum;i++){
			for (j = 1;j <= MG.vexnum;j++){
				if(MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH){
					edge[count].start = i;
					edge[count].end = j;
					edge[count].cost = MG.arcs[i][j];
					count++;
				}
			}
		}
	}
	else{
		for(i = 1; i <= MG.vexnum;i++){
			for (j = i;j <= MG.vexnum;j++){
				if(MG.arcs[i][j] != 0 && MG.arcs[i][j] != UN_REACH){
					edge[count].start = i;
					edge[count].end = j;
					edge[count].cost = MG.arcs[i][j];
					count++;
				}
			}
		}
	}
	
}




/* *
 *　將邊按權值從大到小排序
 * */
void sort_edge(Edge edge[],int arcnum){
	int i,j;
	Edge temp;
	for(i = 0; i < arcnum - 1;i++){
		for (j = i+1;j < arcnum;j++){
			if(edge[i].cost > edge[j].cost){
				temp = edge[i];
				edge[i] = edge[j];
				edge[j] = temp;
			}
		}
	}
}

/* *
 * 輸出邊的信息
 * */
void print_edge(Edge edge[],int arcnum){
	int i = 0;
	while(i < arcnum){
		printf(%d,%d,%d
,edge[i].start,edge[i].end,edge[i].cost);
		i++;
	}
}
/**
*    找出指定節點的所屬的連通分量，這裡是找出其根節點在father數組中下標。
**/ int findFather(int father[],int v){
	int t = v;
	while(father[t] != -1)
		t = father[t];
	return t;
}

/* *
 *Kruskal算法求最小生成樹
 * */ 
void Kruskal_MG(MGraph MG,Edge edge[]){
	int father[MAX_VEX_NUM];
	int i,count,vf1,vf2;
	// 初始化father數組
	for(i = 0;i < MAX_VEX_NUM;i++){
		father[i] = -1;
	}
	i = 0;
	count = 0; // 統計加入最小生樹中的邊數
	// 遍歷任意兩個結點之間的邊
	while(i < MG.arcnum && count < MG.arcnum){
		vf1 = findFather(father,edge[i].start);
		vf2 = findFather(father,edge[i].end);
		// 如果這兩個節點不屬於同一個連通分量，則加入同一個連通分量
		if (vf1 != vf2){
			father[vf2] = vf1;
			count++;
			printf(%c,%c,%d
,MG.vexs[edge[i].start],MG.vexs[edge[i].end],edge[i].cost);
		}
		i++;
	}
}
/**
 * 主函數
 */
int main(void) {
	MGraph MG;
	Edge edge[MAX_ARC_NUM];
	create_MG(&MG);
	print_MG(MG);
	init_edge(MG,edge);
	sort_edge(edge,MG.arcnum);
	printf(the result of Kruskal:
);
	Kruskal_MG(MG,edge);

		
	
	return EXIT_SUCCESS;
}

運行演示：

jesson@jesson-K43SV:~/develop/worksapce/c_learning/最小生成樹$ gcc -o Kruskal Kruskal.c
jesson@jesson-K43SV:~/develop/worksapce/c_learning/最小生成樹$ ./Kruskal 
Please input graph type DG(0) or UDG(1) :0
Please input vexmun : 4
Please input arcnum : 5
Please input 1th vex(char):a  
Please input 2th vex(char):b
Please input 3th vex(char):c
Please input 4th vex(char):d
Please input 1th arc v1(char) v2(char) weight(int): a b 1
Please input 2th arc v1(char) v2(char) weight(int): a c 3
Please input 3th arc v1(char) v2(char) weight(int): a d 4
Please input 4th arc v1(char) v2(char) weight(int): b c 2 
Please input 5th arc v1(char) v2(char) weight(int): c d 3
Graph type: Direct graph
Graph vertex number: 4
Graph arc number: 5
Vertex set:
 a	b	c	d	
Adjacency Matrix:
0	1	3	4
1000	0	2	1000
1000	1000	0	3
1000	1000	1000	0
the result of Kruskal:
a,b,1
b,c,2
c,d,3