数据结构课程设计求最小生成树.doc
文本预览下载声明
##大学
数据结构课程设计报告
题目： 图的最小生成树
院（系）：
学生姓名:
班级： 学号:
起迄日期:
指导教师:
指导教师评语：
指导教师评语： 成绩：
签名：
年 月 日
2011—2012年度 第 2 学期
一、需求分析
1.问题描述：
设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
该题目需要运用最小生成树来解决。最小生成树的代价之和最小，所以是一种最经济的架设方法。
2.基本功能
该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。
3.输入输出
首先输入顶点的个数以及边的个数，格式如:4 6。然后输入边的权值，格式如：a b 1。输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。最小生成树的格式为：顶点名 顶点名权值。
二、 概要设计
1.设计思路：
问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。
1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。
2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
2.数据结构设计：
1.抽象数据类型如下：
ADT Graph
{ 数据对象 V：v是具有相同特征的数据元素的集合，称为顶点集。
数据关系 R：R={VR}
VR={v,w|v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧v,w的意义或信息}
基本操作：
GreatGraph（G,V,VR）；
初始条件：V是图的顶点集，VR是图中弧的集合。
操作条件：按V和VR的定义构造图G。
2）LocateVex（G,u）；
初始条件：图G存在，u和G中顶点有相同的特征。
操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
2.存储结构
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];//定义一个顶点数组
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;
typedef struct arcnode//弧结点
{
int adjvex;//该弧指向的顶点的位置
struct arcnode *nextarc;//弧尾相同的下一条弧
char *info;//该弧信息
}arcnode;
typedef struct vnode//邻接链表顶点头接点
{
char data;//结点信息
arcnode *firstarc;//指向第一条依附该结点的弧的指针
}vnode,adjlist;
3.软件结构设计：
开始
开始
创建一个图
功能选择
1.建立邻接矩阵
2.建立邻接表
3. PRIM算法
4.
kruscal算法
结束
三、 详细设计
1．主函数和其他函数的伪码算法
主函数：
void main()
{
algraph gra;
MGraph_L G;
int i,j,d,g[20][20];
char a=a;
d=creatMGraph_L(G);
creatadj(gra,G);
cout**********************************endl;
cout**1。用邻接矩阵存储：*************endl;
cout**2。用邻接表存储：***************endl;
cout**3。PRIM算法求最经济的架设方法***endl;
cout**4。KRUSCAL算法最经济的架设方法**endl;
cout**********************************endlendl;
int s;
显示全部