建立通信网络

滨江学院

《数据结构》课程设计

题 目 建立通信网络

学 号 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={|v.w且P（V,W）,表示V到W的弧，

谓词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; 关键代码输出最小生成树 ·········································································· 以下是主函数部门

int main(void)//主函数 { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf(\ exit(1); } CreatGraph(G); MiniSpanTree(G); system(\ return 0; }

主函数通过调用不同的函数模块来实现的功能 ·········································································· 以下是函数关系的调用图

Main( )

________________________________

CreatGraph() MiniSpanTree( ) ________________

Sort ( ) Find( )

Swapn( )

4.调试分析

1由于对函数调用关系不是非常清楚，导致在程序设计的时候思路不是非常的清晰 2该程序只能满足图顶点比较少的最小生成树的实现，如果用户要求更大的空间，可以在创建图的时候开辟更大的空间。

3在程序输入的时候，必须顶点数值小的先输入，否则程序将会出错。这也是程序应该改进的地方。 4算法的时空分析

1，对矩阵的初始化，设输入一个n个顶点的图，那个将要对矩阵的nxn个元素进行初

始化，所以时间复杂度为O(N2)

2,输入权值和边的时间复杂度为O(n),所以构建图的时间复杂度为O(N2+N) 3.矩阵输出的时间复杂度为O(N2) 。空间复杂度为S（N2）

4在求最小生成树函数中，对边进行标记的时间复杂度为O(N2)。对权值进行排序的时间复杂度为O(N2)，对parent数组赋值的时间复杂度为o(n),所以该函数的时间复杂度为O（2N2+N）

5 过这次课程设计，一方面我加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解，另一方面，使我在序设计方法（如抽象数据类型、结构化分析、模块化设计和结构化设计）、C语言程序调试和测试方面受到比较系统的严格的训练。

5.用户使用说明

1,输入图的顶点数和边数

2任意输入两个图中连接的顶点 3输入这两个顶点的权值 具体步骤图如下

输入完数据之后，按enter键将会显示以下结果

最后按任意键退出，可以进行其他图最小生成树的实现

6.测试结果

这里提供其他几组测试数据：

输入的数据： 输出数据

输入数据： 输出数据：

7.附录；源程序

#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);//权值、头顶点、尾顶点交换 void CreatGraph(MGraph *G)//构件图 { int i, j,n, m; printf(\请输入边数和顶点数:\\n\ scanf(\

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(\ while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf(\输入的数字不符合要求 请重新输入:\\n\ scanf(\ } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf(\请输入%d与%d之间的权值:\\n\ scanf(\ } printf(\邻接矩阵为:\\n\ for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf(\ } printf(\ } }

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\\n\ } }

void Swapn(edge *edges,int 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++) { 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[m] = n; printf(\ %d\\n\ } } }

int Find(int *parent, int f)//找尾 { while ( parent[f] > 0) { f = parent[f]; }

return f; }

int main(void)//主函数 { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf(\ exit(1); } CreatGraph(G);

MiniSpanTree(G); system(\ return 0; }

本文来源：https://www.bwwdw.com/article/zvho.html