最小生成树课程设计(共19页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
湖南人文科技学院计算机科学技术系
科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。
本课程设计我们要解决的问题是图最小生成树问题。要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。
本课程设计要解决的问题构造连通网的最小生成树 ,我们首先要做的是创建一个邻接矩阵，用以来存储图，然后我们要想好怎样利用普里姆算法和克鲁斯卡尔算法来构造最小生成树。把这两种算法写入主函数，调试好程序。最后写好报告。
二、设计目的与任务
1、课程设计目的
本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。
2、课程设计的任务
问题描述: 已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
三、设计方案
1、需求分析
1) 建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；。
2) 利用普里姆算法和克鲁斯卡尔算法求网的最小生成树
3) 按顺序输出生成树中各条边以及它们的权值。
2、概要设计
抽象数据类型(ADT)如下：
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>的意义或信息}
基本操作：
CreatGraph(&G,V,VR)；
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
LocateVex(G, u)；
初始条件：图G存在,u和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
DestoryGraph(&u)；
初始条件：图G存在。
操作结果：销毁图G。
GetVex(G, v)；
初始条件：图G存在，v是图中某个顶点。
操作结果：返回v的值。
NextAdjVex(G, v, w)；
初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。
操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。
BFSTraverse(G, Visit( ))；
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit( )失败，则操作失败。}
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
存储结构
Typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
Typedef struct
{
djMatrix arc;
int vexnum, arcnum;
} MGraph;
流程图
2、用prim算法求解最小生成树
3、用kruskal算法最最小生成树
功能选择
开 始
1、建立邻接矩阵
结 束
3、详细