最小生成树问题中北大学数据结构课程设计资料VIP专享VIP免费

中北大学数据结构与算法课程设计说 明 书学院 、 系 ：软件学院专业：软件工程班级：学 生 姓 名：学 号：设 计 题 目：最小生成树问题起迄日期 : 2015 年 1 月 12 日- 2015 年 1 月 29 日指导教师 :王秀娟2015 年 1 月 29 日1 1 需求分析1.1 已知一个无向连通网表示n 个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市， 边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于 n 个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。1.2 该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。1.3 实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。1.4 程序通过人机交互实现数据的输入和输出。2 选题要求设计内容：在 n 个城市之间建设网络， 只需保证连通即可， 求最经济的架设方法。存储结构采用 （邻接表和邻接矩阵）两种，采用课本上的两种求解算法。设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。3 程序设计方法及主要函数介绍ADT Graph{ 数据对象 V;V 是具有相同特性的数据元素的集合，成为顶点集。数据关系 R：R = {VR} VR = { （v,w ）|v,w 为 V 集合中的元素， （ v,w）表示 v 和 w之间存在的路径} 基本操作 P; CreateMGraph(MGraph *G) 初始条件： V 是图的顶点集，VR是图的边的集合。操作结果：按V 和 VR的定义构造图G，用邻接矩阵存储。CreateALGraph(ALGraph *G) 2 初始条件： V 是图的顶点集，VR是图的边的集合。操作结果：按V 和 VR的定义构造图G，用邻接表存储。LocateVex （G，u）初始条件：图G存在， u 和 G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。MiniSpanTree_PRIM （G, u) 初始条件：图G存在， u 是图 G中的一个顶点。操作结果：用普利姆算法从第u 个顶点出发构造网G的最小生成树T，输出 T 的各条边。Kriuskal(G) 初始条件：图G存在操作结果：用克鲁斯卡尔算法构造图G的最小生成树T，输出 T 的各条边。ListToMat(MGraph *G1,ALGraph *G2) 初始条件：图G2存在操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图G1表示。MatToList(MGraph *G1,ALGraph *G2) 初始条件：图...