滨江学院
《数据结构》课程设计
题 目 建立通信网络
学 号 20112346051
学生姓名 刘 勇
院 系 计算机系
专 业 11级 网络工程
指导教师 宣文霞
二Ｏ一二 年 12 月 10 日
建立通信网络
一。需求分析：
题目：最小生成树kruskal算法的实现
问题描述：任意创建一个图，用kruskal算法求去他的最小生成树。
举例：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，我们可以用求kruskal算法求这个网的最小生成树来解决这个问题。
（1） 建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储
顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值； （2）利用克鲁斯卡尔算法求网的最小生成树； （3）按顺序输出生成树中各条边以及它们的权值。
输入的形式和输入值的范围：输入的数值有各顶点，两顶点之间的权值。输入的顶点最多不能大于20个。
输出的形式：先输出图的邻接矩阵，输出权值的排序，最后输出最小生成树的各边和权值。
程序所能达到的功能；用户可以任意的输入一个顶点小于20的图，该程序可以求出图的邻接矩阵和最小生成树。
D测试数据：6 5 1 2 1 2 3 2 3 4 3 4 5 4 1 5 6 3 2 4 5 输出结果： 《V1, V2》 1 《V2, V3》 2 《V3, V4》 3 《V4,V5》 4
二。概要分析
1 本程序中用到的所有抽象数据类型的定义 ADT Graph{
数据对象V：V是具有向他特性的数据元素的集合，称为顶点集。 数据关系对象： R={VR}
VR={
谓词P（V，W）定义了弧
基本操作P：
CreateCraph(&G,V,VR);
初始条件：V是图的顶点集，VR是图中的弧的集合。 操作结果：按V和VR的定义构造图G..
MiniSpanTree(G);
初始条件：图G存在。
操作结果：求出图G的最小生成树 Sort(edge* ,MGraph *);
初始条件：图G存在，edge存在。 操作结果; 对edge进行了排序。 Swapn(edge *, int x, int y);
初始条件：edge存在，x,y是两条边 操作结果：交换了x,y这两条边。 Find(int *, int );
初始条件：edge存在:
操作结果：对这些边进行遍历查找。
2主程序的流程
int main(void)//主函数 {
MGraph *G;
程序中定义一个图
G = (MGraph*)malloc(sizeof(MGraph)); 为这个图动态分配存储空间 if (G == NULL) {
printf(\ exit(1); }
如果这个图不存在系统将会非正常结束 CreatGraph(G);
创建一个图 {
输入总边数和总顶点
输入各顶点和顶点之间的权值 输出该图的邻接矩阵 }
MiniSpanTree(G); 求该图的最小生成树 {
对权值进行排序
输出排序后的权值和顶点
对各边依次进行判断，是否存在回路，如果没有回路，则输出这条边，否则，则不输出 } system(\
程序运行暂停 return 0;
3序模块之间的层次（调用）关系 主函数模块
图构建模块
最小生成树模块
3.详细设计
#define M 20 #define MAX 20
规定该程序所能创建图的最大顶点数为20个点 typedef struct //用结构体定义边 { }edge;
typedef struct//用结构体定义数组 {
}AdjMatrix[MAX][MAX];
typedef struct//用结构体定义一个图 {
}MGraph;
函数申明
void CreatGraph(MGraph *); //图构建函数申明 void sort(edge* ,MGraph *); //权值排序函数申明
void MiniSpanTree(MGraph *); //生成最小树函数的申明 int Find(int *, int );// 尾顶点查找
void Swapn(edge *, int, int);//权值、头顶点、尾顶点交换 void CreatGraph(MGraph *G)//构件图 { printf(\请输入边数和顶点数:\\n\
G->arc[i][j].adj = G->arc[j][i].adj = 0;//先把矩阵中所有元素赋值为0 for ( i = 1; i <= G->arcnum; i++)//输入边和权值
G->arc[n][m].adj = G->arc[m][n].adj = 1;//将输入的顶点记录为1 getchar(); printf(\请输入%d与%d之间的权值:\\n\ printf(\邻接矩阵为:\\n\输出邻接矩阵 ··········································································· 以上是图的创建，邻接矩阵的建立将辅助权值排序
void MiniSpanTree(MGraph *G)//生成最小生成树 { }
sort(edges, G);//sort函数调用，对权值进行排序
void sort(edge edges[],MGraph *G)//对权值进行排序
void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
在对权值排序时，若(edges[i].weight > edges[j].weigh)调用函数swapn交换这两条
边的权值以及头和尾顶点 ········································································ 以上是对权值进行排序，排序之后将有利于回路的判断，从而求出最小生成树
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[m] = n; printf(\ %d\\n\ } } }
int Find(int *parent, int f)//找尾 { while ( parent[f] > 0) { f = parent[f]; }
return f; 关键代码输出最小生成树 ·········································································· 以下是主函数部门
