#include <stdio.h>
#include <stdlib.h>
#define VertexMax 20 //最大頂點(diǎn)數(shù)為20

typedef char VertexType;

// 采用 邊集數(shù)組 存儲(chǔ)圖中的邊 
typedef struct{
	VertexType begin;
	VertexType end;
	// 邊上的權(quán)值 
	int weight;
}Edge;//邊集數(shù)組 edge[]的單元 

typedef struct{
	//頂點(diǎn)數(shù)組 
	VertexType Vertex[VertexMax];
	//邊集數(shù)組 
	Edge edge[VertexMax];
	//頂點(diǎn)數(shù) 
	int vexnum;
	//邊數(shù) 
	int edgenum;
}EdgeGraph;

void CreateEdgeGraph(EdgeGraph *E){
	int i;
	// 1.輸入頂點(diǎn)數(shù)和邊數(shù)
	printf("請輸入頂點(diǎn)數(shù)和邊數(shù):\n");
	printf("頂點(diǎn)數(shù) n = "); 
	scanf("%d", &E->vexnum);
	printf("邊 ?數(shù) e = "); 
	scanf("%d", &E->edgenum);
	printf("\n"); 
	
	// 2.輸入頂點(diǎn)元素 
	printf("輸入頂點(diǎn)(無需空格隔開):"); 
	scanf("%s", &E->Vertex);
	printf("\n\n");
	
	printf("輸入邊信息和權(quán)值(如：A B 15):\n");
	for(i = 0; i < E->edgenum; i++){
		printf("請輸入第 %d 邊的信息:", i+1);
		scanf(" %c %c %d", &E->edge[i].begin, &E->edge[i].end, &E->edge[i].weight);
	}	
}

void print(EdgeGraph *E){
	int i;
	
	printf("-----------------------------------\n"); 
	printf(" 頂點(diǎn)數(shù)組Vertex:");
	for(i = 0; i < E->vexnum; i++){
		printf("%c ", E->Vertex[i]);
	}
	printf("\n\n");
	
	printf(" 邊集數(shù)組edge:\n\n");
	printf("\t\tBegin	End	Weight\n");
	for(i = 0; i < E->edgenum; i++){
		printf("\tedge[%d]	%c	%c	%d\n", i, E->edge[i].begin, E->edge[i].end,E->edge[i].weight);
	}
	printf("-----------------------------------\n");
}

int partition(EdgeGraph *E, int low, int high){
	Edge pivot = E->edge[low];

	while(low < high){
		while(low < high && pivot.weight <= E->edge[high].weight){
			high--;
		}
		E->edge[low] = E->edge[high];
		
		while(low < high && E->edge[low].weight <= pivot.weight){
			low++;
		}
		E->edge[high] = E->edge[low];
	}
	E->edge[low] = pivot;
	// 返回 中間位置 
	return low;
}

// 將 圖中的邊 從小到大進(jìn)行排序 (快速排序)
void quickSort(EdgeGraph *E, int low, int high){
	// 遞歸出口條件 
	if(low < high){
		// 劃分 
		int pos = partition(E, low, high);
	
		quickSort(E, low, pos - 1);
		quickSort(E, pos + 1, high);
	}
} 

//查找元素v在一維數(shù)組 Vertex[] 中的下標(biāo)，并返回下標(biāo) 
int LocateVertex(EdgeGraph *E, VertexType v){
	int i;
	for(i = 0; i < E->vexnum; i++){
		if(v == E->Vertex[i]){
			return i; 
		} 
	}
	printf("No Such Vertex!\n");
	return -1;
}

// 參數(shù) v：結(jié)點(diǎn)在Vertex數(shù)組中的下標(biāo) 
int FindRoot(int v,int parent[]){
	//parent=-1表示沒有雙親，即沒有根節(jié)點(diǎn) 
	while(parent[v] != -1){
		//逐代查找根節(jié)點(diǎn) 
		v = parent[v];
	}
	//將找到的根節(jié)點(diǎn)返回，若沒有根節(jié)點(diǎn)，返回自身 
	return v;
}

void outputMST(EdgeGraph *E, int i){
	printf("%c — %c, w = %d\n", E->edge[i].begin, E->edge[i].end, E->edge[i].weight);//輸出此邊 
}

// 最小生成樹-克魯斯卡爾算法算法 
void MiniSpanTree_Kruskal(EdgeGraph *E){
	int i;
	//生成邊計(jì)數(shù)器，當(dāng) num = 頂點(diǎn)數(shù)-1 時(shí)，最小生成樹生成完畢 
	int num;
	int root1, root2; 
	int LocateV1, LocateV2; 
	//用于查找頂點(diǎn)的雙親，判斷兩個(gè)頂點(diǎn)間是否有共同的雙親，來判斷生成樹是否會(huì)成環(huán) 
	int parent[VertexMax];
	
	//1.按權(quán)值從小到大排序 
	printf("排序前的邊集數(shù)組：\n");
	print(E); 
	quickSort(E, 0, E->edgenum -1);
	printf("排序后的邊集數(shù)組：\n");
	print(E);
	
	//2.初始化parent數(shù)組 
	for(i = 0; i < E->vexnum; i++){
		// 視 圖中所有頂點(diǎn) 都是 一棵只有根結(jié)點(diǎn)的樹 
		parent[i] = -1;
	}
	
	printf("\n 最小生成樹(Kruskal):\n\n");
	//3. for循環(huán)，遍歷 edge邊數(shù)組 
	for(num = 0, i = 0; i < E->edgenum; i++){
		LocateV1 = LocateVertex(E, E->edge[i].begin);
		LocateV2 = LocateVertex(E, E->edge[i].end);
		// 找到 所在生成樹的根結(jié)點(diǎn) 
		root1 = FindRoot(LocateV1, parent);
		root2 = FindRoot(LocateV2, parent);
	
		// 若不會(huì)成環(huán)，則在最小生成樹中構(gòu)建此邊
		// 根結(jié)點(diǎn)不相等 即 在不同的連通分量中 
		if(root1 != root2){
			// 輸出該邊 
			outputMST(E, i);
			//合并生成樹，將 root1 作為 根結(jié)點(diǎn)，即 root2 的雙親為 root1 
			parent[root2] = root1;
			// 最小生成樹邊數(shù) + 1 
			num++;
			
			//若num=頂點(diǎn)數(shù)-1，代表樹生成完畢，提前結(jié)束 
			if(num == E->vexnum-1){
				return;
			}
		} 
	}
}

int main(){
	EdgeGraph E;
	CreateEdgeGraph(&E);
	MiniSpanTree_Kruskal(&E);
	
	return 0;
}