最小生成树的应用数据结构课程设计

摘 要

求一个网的最小生成树，即以最低的经济建设n个城市之间的通信网，利用普里姆算法和克鲁斯卡尔算法求这个网的最小生成树。

关键词：网的最小生成树；Kruskal算法；Prim算法；边和权值。

目 录

1 问题描述 ................................................................................................ 1 2 需求分析 ................................................................................................ 1 3 概要设计 ................................................................................................ 1 3．1抽象数据类型定义 ..................................................................... 1 3．2模块划分 ..................................................................................... 3 4 详细设计 ................................................................................................ 5 4．1数据类型的定义 ......................................................................... 5 4．2主要模块的算法描述 ................................................................. 5 5 测试分析 .............................................................................................. 13 6 课程设计总结 ...................................................................................... 13 参考文献 .................................................................................................. 16 附录（源程序清单） .............................................................................. 17

1 问题描述

若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济建设这个通信网，是一个网的最小生成树。

2 需求分析

（1）.可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。

（2）.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。利用克鲁斯卡尔算法和普利姆算法实现。

3 概要设计

3．1抽象数据类型定义 1.ADT Graph

{ 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR}

VR={<v,w>|v,w属于v且p(v,w),(v,w)表示从v到w的弧，

谓词p(v,w)定义了弧<v,w>的意义或信息}

基本操作：

(1) CreatGraph(&G,V,VR)；

初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。

(2) LocateVex(G, u)；

初始条件：图G存在,u和G中顶点有相同的特征。

操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回

其他信息。

(3) DestoryGraph(&u)；

初始条件：图G存在。 操作结果：销毁图G。

(4) GetVex(G, v)；

初始条件：图G存在，v是图中某个顶点。 操作结果：返回v的值。

(5) NextAdjVex(G, v, w)；

初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的

最后一个邻接点，则返回“空”。

(6) BFSTraverse(G, Visit( ))；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数

Visit一次且仅一次。一旦visit( )失败，则操作失败。}

2. 存储结构 Typedef struct {

int adj;

int weight; }AdjMatrix[MAX][MAX]; Typedef struct {

djMatrix arc; int vexnum, arcnum; } MGraph;

3．2模块划分

本程序包括五个模块： （1）主函数模块

(2) 邻接矩阵定义模块代码

typedef struct ArcCell{ int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct {

char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;

int localvex(MGraph_L G,char v)

{ int i=0; while(G.vexs[i]!=v) { ++i;} return i;}

(3) 创建链接矩阵模块代码

int creatMGraph_L(MGraph_L &G) { char v1,v2; int i,j,w;

cout<<"…创建无向图（城市分布图）…"<<endl;cout <<"请输入图G顶点（城市）和弧（边）的个数:(4 6)不包括“()”"<<endl; cin>>G.vexnum>>G.arcnum; for(i=0;i!=G.vexnum;++i)

{ cout<<"输入顶点（城市）"<<i<<endl;

cin>>G.vexs[i]; } for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

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

for(int k=0;k!=G.arcnum;++k)

{ cout<<"输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包

括“()”"<<endl; cin>>v1>>v2>>w;

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

cout<<"图G邻接矩阵创建成功！"<<endl; return

G.vexnum;}

(4)最小生成树Prim算法及代价模块代码 (5)最小生成树kruskal算法及代价模块代码

4 详细设计

4．1数据类型的定义

（1）树类型

#define MAXVALUE 100 #define MAXLEAF 50

#define MAXNODE MAXLEAF*2-1;

（2）图类型