#include
#include
#define?M?20
#define?MAX?20

typedef?struct
{
	int?begin;
	int?end;
	int?weight;
}edge;

typedef?struct
{
	int?adj;
	int?weight;
}AdjMatrix[MAX][MAX];

typedef?struct
{
	AdjMatrix?arc;
	int?vexnum?arcnum;
}MGraph;

void?CreatGraph（MGraph?*）;//構造圖函數
void?sort（edge*?MGraph?*）;//排序函數
void?MiniSpanTree（MGraph?*）;//生成最小生成樹函數
int??Find（int?*?int?）;//找到最后的結點
void?Swapn（edge?*?int?int）;//交換權值?以及頭和尾


int?main（void）//主函數
{
	MGraph?*G;
	G?=?（MGraph*）malloc（sizeof（MGraph））;
	if?（G?==?NULL）
	{
		printf（“申請內存失敗！“）;
		exit（1）;
	}
	CreatGraph（G）;
	MiniSpanTree（G）;
	return?0;
}

void?CreatGraph（MGraph?*G）//構造圖函數
{
	int?i?jn?m;
	printf（“請輸入邊數和頂點數:“）;
	scanf（“%d?%d“&G->arcnum&G->vexnum）;
	for?（i?=?1;?i?<=?G->vexnum;?i++）//初始化圖
	{
		for?（?j?=?1;?j?<=?G->vexnum;?j++）
		{
			G->arc[i][j].adj?=?G->arc[j][i].adj?=?0;
		}
	}
	for?（?i?=?1;?i?<=?G->arcnum;?i++）//輸入邊和權值
	{
		printf（“請輸入有邊的2個頂點:\n“）;
		scanf（“%d?%d“&n&m）;
		while（n??G->vexnum?||?m??G->vexnum）
		{
			printf（“輸入的數字不符合要求?請重新輸入:“）;
			scanf（“%d%d“&n&m）;
		}
		G->arc[n][m].adj?=?G->arc[m][n].adj?=?1;
		printf（“請輸入%d與%d之間的權值:\n“?n?m）;
		scanf（“%d“&G->arc[n][m].weight）;
	}
	printf（“鄰接矩陣為:\n“）;
	for?（?i?=?1;?i?<=?G->vexnum;?i++）
	{
		for?（?j?=?1;?j?<=?G->vexnum;?j++）
		{
			printf（“%d?“G->arc[i][j].adj）;
		}
		printf（“\n“）;
	}
}


void?sort（edge?edges[]MGraph?*G）//對權值進行排序
{
	int?i?j;
	for?（?i?=?1;?i?arcnum;?i++）
	{
		for?（?j?=?i?+?1;?j?<=?G->arcnum;?j++）
		{
			if?（edges[i].weight?>?edges[j].weight）
			{
				Swapn（edges?i?j）;
			}
		}
	}
	printf（“權排序之后的為:\n“）;
	for?（i?=?1;?i?arcnum;?i++）
	{
		printf（“<>???%d\n“?edges[i].begin?edges[i].end?edges[i].weight）;
	}
}


void?Swapn（edge?*edgesint?i?int?j）//交換權值?以及頭和尾
{
	int?temp;
	temp?=?edges[i].begin;
	edges[i].begin?=?edges[j].begin;
	edges[j].begin?=?temp;
	temp?=?edges[i].end;
	edges[i].end?=?edges[j].end;
	edges[j].end?=?temp;
	temp?=?edges[i].weight;
	edges[i].weight?=?edges[j].weight;
	edges[j].weight?=?temp;
}

void?MiniSpanTree（MGraph?*G）//生成最小生成樹
{
	int?i?j?n?m;
	int?k?=?1;
	int?parent[M];
	edge?edges[M];
	for?（?i?=?1;?i?vexnum;?i++）//只取鄰接矩陣的下三角放入edges
	{
		for?（j?=?i?+?1;?j?<=?G->vexnum;?j++）
		{
			if?（G->arc[i][j].adj?==?1）
			{
				edges[k].begin?=?i;
				edges[k].end?=?j;
				edges[k].weight?=?G->arc[i][j].weight;
				k++;
			}
		}
	}
	sort（edges?G）;
	for?（i?=?1;?i?<=?G->arcnum;?i++）
	{
		parent[i]?=?0;
	}
	printf（“最小生成樹為:\n“）;
	for?（i?=?1;?i?<=?G->arcnum;?i++）//核心部分
	{
		n?=?Find（parent?edges[i].begin）;
		m?=?Find（parent?edges[i].end）;
		if?（n?!=?m）
		{
			parent[n]?=?m;
			printf（“<>???%d\n“?edges[i].begin?edges[i].end?edges[i].weight）;
		}
	}
}

int?Find（int?*parent?int?f）//找到最后的結點
{
	while?（?parent[f]?>?0）
	{
		f?=?parent[f];
	}
	return?f;
}