最小生成树实验报告
- 格式：doc
- 大小：108.00 KB
- 文档页数：9
. .. 数据结构课程设计报告
题目： 最小生成树问题 院（系）： 计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 指导教师:
2011—2012年度 第 2 学期 一、需求分析 . .. 1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
2.基本功能
在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出
以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。
二、 概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所 以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={|v,w∈V且P(v,w)，表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息} 基本操作： CreateGraph( &G, V, VR ) 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph( &G ) 初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 . .. 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w ) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧，若G是无向的，则还增添对称弧 。 DeleteArc( &G, v, w ) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧，若G是无向的，则还删除对称弧 。 DFSTraverse( G, Visit() ) 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用 函数Visit一次且仅一次。一旦visit()失败，则操作失败。 BFSTraverse( G, Visit() ) 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用 函数Visit一次且仅一次。一旦visit()失败，则操作失败。 }ADT Graph . .. 存储结构： 邻接矩阵： #define INFINITY INT_MAX//最大值无穷 #define MAX_VERTEX_NUM 20//最大顶点个数 typedef enum{UDN} GraphKind; typedef struct ArcCell{ VRType adj;//VRType是顶点关系类型 //对带权图为权值类型 InfoTyep *info;//该弧相关信息的指针 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ VertexType vexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum,arcnum;//图的当前顶点数和弧数 GraphKind kind; }MGraph;
三、 详细设计 1.数据类型的定义 <1>图类型 #define M 20 #define MAX 20 #define null 0 #define MAX_VERTEX_NUM 20// 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_INFO 20 // 相关信息字符串的最大长度+1 #define INFINITY INT_MAX// 用整型最大值代替∞ typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_NAME];// 邻接矩阵的数据结构 typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示 相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) . .. }ArcCell, adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的数据结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM];// 顶点向量 adjMatrix arcs;// 邻接矩阵 int vexnum,// 图的当前顶点数 arcnum;// 图的当前弧数 } mGraph; // 记录从顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct { VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; 2.主要模块的算法描述 <1>主函数 int main(void) //主函数 { int i; scanf("%d",&i); switch(i) /*选择菜单*/ { case 1:{ 用prim算法求最小生成树 }break; case 2:{ 用kruskal算法求最小生成树 }break; default:printf("\t\t输入错误！请重新输入！\n"); } } <2>使用prim算法生成最小生成树 { 定义图的数据结构； 图的构建； {/*prim算法求最小生成树*/ . .. 对I,j,k定义； 记录从顶点集U到V-U的代价最小的边的辅助数组定义； 把顶点信息的赋给k； 辅助数组初始化； 令最小代价初始化为0，closedge[k].lowcost=0; // 初始,U={u}； 满足当循环变量i小于图的当前节点数时循环； { 按照选取最小代价法则（即求closedge.lowcost的最小正值）选取当 前节点的下一结点（第k顶点）； 输出生成树的边； 将第k顶点并入U集合； 满足循环变量j小于图的当前点数时循环； { 新顶点并入U集后重新选择最小边； } } } } <3>使用克鲁斯卡尔算法生成最小生成树 { 图的构建并初始化 { 定义图的数据结构； 申请节点空间(如果失败则返回信息)； 创建图； /*kruskal算法求最小生成树*/ { 对i,j,n,m, parent[M],edge edges[M]定义或初始化； 满足当循环变量i小于图的当前节点数时循环； { 满足循环变量j=i+1小于图的当前点数时循环； { if(第i个顶点于第j个顶点相连) { 把i赋给edges[k].begin； 把j赋给edges[k].end； . .. 把i，j之间的权值赋给edges[k].weight； K++；}/*对结构体edge进行初始化*/ } } 对图G边的权值进行排序sort(edges, G)； 当循环变量i小于当前弧度数时 {将0赋给parent[i]，初始化数组；} 当循环变量i小于当前弧度数时(此时第i条弧为最小的) { 找第i条弧的起点和终点；并分别赋给你n，m； 当n，m不相等时 {把m赋给parent[n]； 输出此时第i条弧的起点、终点、权值； } } }
流程图：
四、 调试分析 本次课程设计基本达到了设计需求。但是还有很多不足。比如不能随意切换两种算法，也不能由用户选择使用邻接矩阵还是邻接表，以后更加深入的学习计算机知识或许可以在这两个方面进行改进。
五、测试结果 prim算法正确结果：
主函数 Prim算法 克鲁斯卡尔算法
