构成可以使n个城市连接的最小生成树

姓 名: 学 号: 专 业: 班 级: 指导教师: 职 称:

熊 彬 100912042 电子信息工程 电信1021 梁 英

讲师

计算机与电子工程学院

2012年1月

课程设计(实习)评审表

姓 名 熊彬 学 院 电子信息工程 学 号 专业班级 100912042 电信1021 题 目 构成可以是n个城市连接的最小生成树 职称 评审时间 年 月 日 评 审 意 见 评审成绩 指导教师签名

1

课程设计(实习)作品验收表

题目 姓 名 参与人员 班 级 学 号 设计任务与要求： 构成可以使n个城市连接的最小生成树 熊彬 电信1021 100912042 作品完成情况： 验收情况： 验收教师签名：___________ 年 月 日 2

目录

一．需求分析 .................................................................................. 4

1.1 设计的任务..................................................................................................... 4

1.2 程序所能达到的功能..................................................................................... 4 1.3 程序执行命令................................................................................................. 4

二．概要设计 .................................................................................. 5

2.1 抽象数据类型结构体数组的定义：............................................................. 5

2.2 程序模块......................................................................................................... 6 2.3流程图.............................................................................................................. 6

三．详细设计 .................................................................................. 7

3.1 数据类型定义................................................................................................. 7

3.2 程序主要模块................................................................................................. 7

四．调试分析和测试结果 ............................................................ 9

4.1 调试分析......................................................................................................... 9 4.2测试结果........................................................................................................ 10

五．总结 ........................................................................................ 11 六．参考文献 ................................................................................ 11 七．致谢 ........................................................................................ 12 八．附录 ........................................................................................ 12

3

构造可以使N个城市连接的最小生成树

一．需求分析

1.1 设计的任务

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 1.2 程序所能达到的功能

1.2.1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。

1.2.2 显示出城市间道路网的邻接矩阵。

1.2.3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。

1.3 程序执行命令

输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal 算法→执行 Prim 算法→输出最小生成树

4

二．概要设计

2.1 抽象数据类型结构体数组的定义：

#ifndef ADJACENCYMATRIXED //防止该头文件被重复引用 #define ADJACENCYMATRIXED //而引起的数据重复定义

#define INFINITY 32767 //最大值∞

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef int VRType; //权值，即边的值 typedef char InfoType; //附加信息的类型，后面使用时会定义成一个指针

typedef char VertexType[MAX_VERTEX_NUM]; //顶点类型

typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}

typedef struct ArcCell { VRType adj; //VRType 是顶点关系类型。对无权图，用 1 或 0 表示相邻否；对带权图，则为权值类型。 InfoType* info; //该弧关系信息的指针

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph;

typedef struct //普里姆算法辅助数组的定义 { VertexType adjvex; VRType lowcost;

}closedge[MAX_VERTEX_NUM];

#endif //结束if

5

2.2 程序模块

MGraph G; //网 G，唯一的全局变量 int main(int argc, char * argv[]); //主函数

Status LocateVex(MGraph G, VertexType v); //判断城市 v 在网 G 中的位置 Status CreateUDN(MGraph &G); //创建网 G 的邻接矩阵 void DisplayNet(MGraph G); //以邻接矩阵的形式显示网 G void MiniSpanTree_KRUSKAL(MGraph G); //最小生成树的 Kruskal 算法 void MiniSpanTree_PRIM(MGraph G, VertexType u); //最小生成树的 Prim 算法 Status Minimum(closedge closeEdge, int n); //Prim 算法中求下一个城市的函数 void DeleteInfo(MGraph &G); //释放堆内存上动态申请的空间

2.3流程图

创建用邻接矩阵表示的城市道路网 输入城市数G.vexnum、 道路数G.arcnum 输入城市名G.vexs[i] 输入表示道路的两个城市及道路值G.arcs[i][j].adj 返回 OK 2.3.1创建邻接矩阵的流程图(N-S图)

6

Prim算法 化辅助数组closeEdge for (i=1; i图2.3.2Prim算法流程图（N-S图）

三．详细设计

3.1 数据类型定义

为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。

用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。 这样就建立起了一个城市到城市之间的道路网。

3.2 程序主要模块

说明：该程序共含5个模块，本人负责其中2个模块构造： 3.2.1 初始化图G

***************LocateVex(MGraph G, VertexType v)****************

7

Status LocateVex(MGraph G, VertexType v); { }

while (strcmp(G.vexs[i], v)) {i++;} 返回 i；

**************** CreateUDN************************* { }

3.2.2PRIM算法

************************** MiniSpanTree_PRIM********* void MiniSpanTree_PRIM(MGraph G, VertexType u) {

定义辅助数组：closedge closeEdge; 初始化：strcpy(closeEdge[j].adjvex, u);

closeEdge[j].lowcost = G.arcs[k][j].adj;

输入城市数、道路数；

for (i=0; i<城市数; ++i) 输入城市名； for (i=0; i<城市数; ++i)

for(j=0; j<城市数; ++j)

初始化邻接矩阵：道路值= INFINITY;

for (i=0; i<城市数; ++i)

for(j=0; j<城市数; ++j)

输入两个城市表示道路，输入道路值；

for (i=1; i在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小

8

值；

}

}

********************** Minimum***************** Status Minimum(closedge closeEdge, int n) {

在辅助数组中找到道路值最小的道路的两点城市：

if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost))

}

返回该城市在 G 中的位置

显示找到的道路； 标记新找到的城市；

四．调试分析和测试结果

4.1 调试分析

4.1.1邻接矩阵初始化

本函数的主要功能是对无向网进行邻接矩阵的初始化。构造这种具有n个顶点和e条边的无向网时，关键需要考虑其时间复杂度O（n^+e*n）,其中对邻接矩阵G.arcs的初始化花费了O（n^）的时间。

4.1.2 Prim 算法

Prim 算法的思路是逐步将城市纳入生成树中，这里面的关键步骤是要找到下一个城市。于是通过讨教别人，写了Status Minimum(closedge closeEdge, int n) 函数，这样就可以在辅助数组中找到道路值最小的道路的两点城市了。

9

4.2测试结果

图4.2.1邻接矩阵初始化运行显示界面

图4.2.2Prim算法运行显示界面

10

五．总结

通过本周的课程设计，我们小组终于圆满完成了课程设计的任务，我也有不少收获。既巩固和加深了对数据结构的理解，认识到《数据结构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。

在以后的学习过程中我将要注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。

六．参考文献

[1].严蔚敏，吴伟民. 数据结构（C语言版）. 清华大学出版社，2007

[2].谭浩强，张基温. C语言程序设计教程（第三版）北京：高等教育出版社，2006 [3].陈维新，林小茶. C++面向对象程序设计教程. 北京：清华大学出版社，2004 [4].苏仕华等.数据结构课程设计. 北京： 机械工业出版社，2005

11

七．致谢

感谢梁英老师对我们《数据结构》课程及其实验的悉心指导，正是因为老师在实验课上的指导，让我能够把书本上的知识化成自己的知识，并运用在编程的过程中。

感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程中出现的一些错误可能无法迅速查出解决，你们的帮助为我节省了宝贵的时间。

衷心感谢！

八．附录

//main

#include #include #include #include

#include \"TypeDefine.h\" #include \"AdjacencyMatrix.h\" #include \"InitializeFunction.h\" #include \"MiniSpanTree_KRUSKAL.h\" #include \"MiniSpanTree_PRIM.h\" #include \"DisplayNet.h\" #include \"DeleteInfo.h\"

MGraph G;

12

//全局变量G

int main(int argc, char * argv[]);//主函数

Status LocateVex(MGraph G, VertexType v);//判断城市 v 在网 G 中的位置 Status CreateUDN(MGraph &G);//创建网 G 的邻接矩阵 void DisplayNet(MGraph G);//以邻接矩阵的形式显示网 G

void MiniSpanTree_KRUSKAL(MGraph G);//最小生成树的 Kruskal 算法 void MiniSpanTree_PRIM(MGraph G, VertexType u);//最小生成树的 Prim 算法 Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数 void DeleteInfo(MGraph &G);//释放堆内存上动态申请的空间

int main(int argc, char * argv[]) { }

CreateGraph(G); DisplayNet(G);

MiniSpanTree_KRUSKAL(G); MiniSpanTree_PRIM(G, G.vexs[0]); DeleteInfo(G); cout<//intializeFunction.h

Status CreateDG(MGraph &G){return 0;}; Status CreateDN(MGraph &G){return 0;}; Status CreateUDG(MGraph &G){return 0;}; Status CreateUDN(MGraph &G);

Status LocateVex(MGraph G, VertexType v) {

13

}

//判断输入的顶点v在G中的位置。

//根据顶点的类型，可重载此函数。目前为char int i=0;

while (strcmp(G.vexs[i], v)) {i++;} return i;

Status CreateGraph(MGraph &G) {

//采用数组（邻接矩阵）表示法，构造图G. G.kind = UDN; //默认构造无向网

/* printf(\"+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\");

switch (G.kind) {

case DG: return CreateDG(G); //构造有向图G case DN: return CreateDN(G); //构造有向网G case UDG: return CreateUDG(G); //构造无向图G case UDN: return CreateUDN(G); //构造无向网G default : return ERROR; }

printf(\"|1:有向图 2:无向图 3:有向网 4:无向网\\n\"); printf(\"|请选择:[ ]\\b\\b\"); scanf(\"%d\.kind);

printf(\"+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\");*/

}//CreateGraph

Status CreateUDN(MGraph &G) {

14

//采用数组（邻接矩阵）表示法，构造图G.

int i, j, k;

VertexType v1, v2; VRType w;

printf(\" 构造可以使N个城市连接的最小生成树\\n\"); printf(\"请输入城市数、道路数(至少6个城市，10条道路)：\"); cin>>G.vexnum>>G.arcnum;

for (i=0; ifor (i=0; i//构造顶点向量

printf(\"请输入第 %d 个城市名（共 %d 个）:\.vexnum); cin>>G.vexs[i];

//初始化邻接矩阵

for (j=0; jG.arcs[i][j].adj = INFINITY;

// G.arcs[i][j].info = NULL; }

printf(\"请输入一条道路连接的两个城市名及权值:\\n\"); for (k=0; kprintf(\"共%3d条道路，第%3d条道路：\.arcnum,k+1); cin>>v1>>v2>>w;

//输入一条边依附的顶点及权值

//构造邻接矩阵

15

i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j].adj = w;

//确定v1、v2在G中的位置

//弧的权值

}

G.arcs[j][i] = G.arcs[i][j]; //置的对称弧

return OK;

}//CreateUDN

//MiniSpan Tree PRIM.h

Status Minimum(closedge closeEdge, int n) { }

void MiniSpanTree_PRIM(MGraph G, VertexType u) {

//用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的int i, flag, minTemp = INFINITY; for (i=0; ireturn flag;

if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) { }

minTemp = closeEdge[i].lowcost; flag = i;

各条边。

16

//记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义见

\"AdjacencyMatrix.h\"

int i, j, k, totalCost=0; closedge closeEdge; k = LocateVex(G, u); for (j=0; jcout<<\"\\n\\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\\\\\n\"; cout<<\"|用Prim算法求最小生成树的各条边依次为：\\n-----\"; closeEdge[k].lowcost = 0;//初始，U={u}; for (i=1; ik = Minimum(closeEdge, G.vexnum);

//求出 T 的下一个结点：第 k

//选择其余 G.vexnum-1 个顶点

if (j != k) { }

strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj;

//辅助数组初始化

顶点

//

此

时

closeEdge[k].lowcost

=

MIN{closeEdge[vi].lowcost

|

closeEdge[vi].lowcost > 0, vi∈V-U}

cout<<'<'<'; //输出生成树的边 totalCost += closeEdge[k].lowcost; closeEdge[k].lowcost = 0;

//第 k 顶点并入 U 集

for (j=0; j17

if (G.arcs[k][j].adj < closeEdge[j].lowcost) //新顶点并入 U 后重新选

择最小边

}

cout<<\"\\n|总代价：\"<cout<<\"+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^/\\n\";

}

{ }

strcpy(closeEdge[j].adjvex, G.vexs[k]); closeEdge[j].lowcost = G.arcs[k][j].adj;

}//MiniSpanTree

18