#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAX 100
#define NO INT_MAX//NO表示没有边，相当于INF

typedef struct Graph
{
	int arcnum;
	int vexnum;
	char vextex[MAX][20];
	int martrix[MAX][MAX];
}Graph;
//邻接矩阵打印输出图
void print_graph(Graph* g)
{
	for (int i = 0; i < g->vexnum; i++)
	{
		printf("\t%s", g->vextex[i]);
	}
	printf("\n");
	for (int i = 0; i < g->vexnum; i++)
	{
		printf("%s\t", g->vextex[i]);
		for (int j = 0; j < g->vexnum; j++)
		{
			if (g->martrix[i][j] == INT_MAX)
			{
				printf("∞\t");
			}
			else
			{
				printf("%d\t", g->martrix[i][j]);
			}
		}
		printf("\n");
	}
}
//定义最小生成树的边结构
typedef struct Arc
{
	int begin;
	int end;
	int weight;//在边结构中加多了一个权值weight来用于判断构造最小生成树
}Arc;
//打印最小生成树
void print_tree(Graph* g, Arc* arc, int count)
{
	printf("最小生成树:\n");
	for (int i = 0; i < count; i++)
	{
		printf("%s--->%s\n", g->vextex[arc[i].begin], g->vextex[arc[i].end]);
	}
}
//比较函数（用于在qsort中，因为qsort是一个泛函数，开始时未知函数类型，需要在调用函数时再给出），
//所以这个比较基准函数需要使用强制类型转换
int compare_arc(const void* a, const void* b)
{
	return(((Arc*)a)->weight-((Arc*)b)->weight);//强制转化为arc类型，根据边结构的weight值进行比较，如果大于则返回正数，等于则返回0，小于则返回负数
}
//克鲁斯卡尔算法
void graph_kruskal(Graph* g)
{
	//定义边结构数组arc用于保存图中存在的边
	Arc* arc = (Arc*)malloc(sizeof(Arc) * g->vexnum * g->vexnum);
	assert(arc);
	int count=0;//count用于存边
	for (int i = 0; i < g->vexnum; i++)
	{
		for (int j = 0; j < g->vexnum; j++)
		{
			if (g->martrix[i][j] != NO)
			{
				(arc + count)->begin = i;
				(arc + count)->end = j;
				(arc + count)->weight = g->martrix[i][j];
				count++;
			}
		}
	}
	//快速排序根据边权值进行排序
	//(注意快速排序是不稳定的，所以选边的顺序不是按照原顺序的)
	qsort(arc,count,sizeof(Arc),compare_arc);
	//定义parent整型数组，大小为顶点数
	int* parent = (int*)malloc(sizeof(int) * g->vexnum);
	assert(parent);
	for (int i = 0; i < g->vexnum; i++)
	{
		parent[i] = i;//初始化时先将每个结点的前驱结点都置为自身
	}
	Arc* result = (Arc*)malloc(sizeof(Arc) * g->arcnum);//result是用于存储对边进行排序后的边结构 
	assert(result);
	count = 0;//count用于跟踪已选的边的数量
	int i = 0;//i用于遍历所有的边
	printf("Kruskal的选边过程如下：\n");
	while (count < g->vexnum - 1)//当边没选够时则继续进行
	{
		int x = (arc + i)->begin;
		int y = (arc + i)->end;
		//初始化两个变量来存x和y的根节点
		int root_x = x;
		int root_y = y;
		while (parent[root_x] != root_x)
		{
			root_x = parent[root_x];//进行压缩路径，将其根节点设为根节点的根节点
		}
		while (parent[root_y] != root_y)
		{
			root_y = parent[root_y];
		}
		if (root_x != root_y)//如果不构成一个环的话
		{
			result[count] = arc[i]; //将该边加入到最小生成树中
			count++;
			printf("选择边：%s---%s,权值为:%d\n",g->vextex[x],g->vextex[y],g->martrix[x][y]);
			parent[root_x] = root_y;//将所选边前面点的前驱节点置为后边的点（也是起到类似压缩路径的效果，谁先谁后好像关系不大）
		}
		i++;
	}
	print_tree(g, arc, count);
	free(arc);
	free(result);
	free(parent);
}

int main()
{
	Graph g = { 10,7,{"A","B","C","D","E","F","G"},
		{
			{NO,50,60,NO,NO,NO,NO},
			{50,NO,NO,65,40,NO,NO},
			{60,NO,NO,52,NO,NO,45},
			{NO,65,52,NO,50,30,42},
			{NO,40,NO,50,NO,70,NO},
			{NO,NO,NO,30,70,NO,NO},
			{NO,NO,45,42,NO,NO,NO}
		} };
	print_graph(&g);
	graph_kruskal(&g);
	return 0;
}