Prim算法详解.doc

《数据结构》课程设计报告 设计题目： 构造可以使n个城市连接的最小生成树 姓名： 吴友文 学号： 211415076 专业： 物联网（嵌入式培养） 院系： 计算机科学与技术学院 班级： 1406 指导教师： 王江涛 2016年 1 月 8 日 摘要 英文摘要 目 录 一、问题描述 题目内容：构造可以使n个城市连接的最小生成树给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。 基本要求： 城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。（要求至少10个城市，15条边） 最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 二、需求分析 本程序的功能包括数组表示候选最短边的集合，邻接矩阵的初始化，Prim算法生成最小生成树。 程序运行后显现提示信息，等候根据提示决定各项信息条件。 用户输入数据完毕，程序将输出运行结束。 测试数据应为邻接矩阵的表达、最小生成树以及最小生成树的代价。 三、概要设计 辅助数组数据类型定义为： struct shortEdge { int lowcost;//权值 int adjvex;//最短边的邻接点 }; 操作集合： (1)MGraph();初始化邻接矩阵 (2)~MGraph(){}析构函数 (3)void CreateMGraph();创建便所对应的顶点序号，以及其权值 (4)void printMGraph();输出邻接矩阵 (5)void Prim();Prim算法生成最小生成树并计算其代价 四、数据结构设计 元素类型 DataType vertex[MaxSize]; //存放顶点的数组 int arcs[MaxSize][MaxSize]; //存放图中边的数组 int versNum, arcsNum; //定点数和边数 shortEdge shortEdge[MaxSize]; //最短边数组大小 MaxSize 30 //全局变量辅助数组大小 INFINITYN 65536 //表示权值无限大 五、算法设计 1、算法分析 首先，采用Prime算法构造最小生成树，Prime算法基于的存储结构为图的存储结构，由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储，那么我们就要实现邻接矩阵的初始化。 然后，我们还需要自定义边所对应的顶点序号以及其权值，所以就要建立一个自定义的成员函数。 其次，题目要求我们输出邻接矩阵，在自定义完的各项数据的基础上，输出邻接矩阵。 最后，Prime算法最小生成树，基本思想是：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 显然，Prime算法的关键是如何找到U和V--U的最短边来扩充生成树T。所以Prime算法基于的另一个存储结构就是候选最短边集：设置一个数组shortEdge[n]表示候选最短边集，数组元素包括adjvex和lowcost两个域，分别表示候选最短边的邻接点和权值。 而最小代价即是最小生成树上边的权值之和。 2、算法实现 LinkList CreateList(void) // { //尾插法建立带头结点的通讯录链表算法 LinkList head=new ListNode; //申请头结点 ListNode *p,*rear; int flag=0; //结束标志置0 rear=head; //尾指针初始指向头结点 while(flag==0) { p=(ListNode *)m