最小生成树问题 要在n个城市之间建役通信网络

一、问题描述 若要在n个城市之间建役通信网络，只福要架设n-1条级路即可．如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 二、基本要求 （1）利用克鲁斯卡尔算法求图的最小生成树。 （2）能实现教科书6.5节中定义的抽象数据类型MFSet.以此表示构造生成树过程中的连通分量。 (3 ) 以文本形式输出生成树中各条边以及他们的权值． 三、需求分析 1、构造图结构。 2、利用克鲁斯卡尔算法求图的最小生成树。 3、完成生成树的输出。

#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 < 0 || n > G->vexnum || m < 0 || n > 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 < G->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 < G->arcnum; i++）
	{
		printf（“<< %d %d >>   %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 < G->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 %d >>   %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;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3137  2008-07-02 11:15  zxscs.cpp

----------- ---------  ---------- -----  ----

                 3137                    1