Prim算法

《Prim算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计《数据结构》课程设计报告设计题目：构造可以使n个城市连接的最小生成树姓名：吴友文学号：211415076专业：物联网（嵌入式培养）院系：计算机科学与技术学院班级：1406指导教师：王江涛2016年1月8日数据结构课程设计《数据结构》课程设计报告设计题目：构造可以使n个城市连接的最小生成树姓名：吴友文学号：211415076专业：物联网（嵌入式培养）院系：计算机科学与技术学院班级：1406指导教师：王江涛2016年1月8日数据结构课程设计摘要数据结构课程设计英文摘要数据结构课程设计目录一、问题描述题目内容：构造可以使n个城市连接的最小

2、生成树给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。1．基本要求：1)城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。（要求至少10个城市，15条边）2)最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。二、需求分析1．本程序的功能包括数组表示候选最短边的集合，邻接矩阵的初始化，Prim算法生成最小生成树。2．程序运行后显现提示信息，等候根据提示决定各项信息条件。3．用户输入数据完毕，程序将输出运行结束。4．测试数据应为邻接矩阵的表达、最小生

3、成树以及最小生成树的代价。三、概要设计1．辅助数组数据类型定义为：structshortEdge{intlowcost;//权值intadjvex;//最短边的邻接点};操作集合：(1)MGraph();初始化邻接矩阵(2)~MGraph(){}析构函数(3)voidCreateMGraph();创建便所对应的顶点序号，以及其权值(4)voidprintMGraph();输出邻接矩阵(5)voidPrim();Prim算法生成最小生成树并计算其代价四、数据结构设计1．元素类型DataTypevertex[MaxSize];//存放顶点的数组inta

4、rcs[MaxSize][MaxSize];//存放图中边的数组intversNum,arcsNum;//定点数和边数shortEdgeshortEdge[MaxSize];//最短边数组大小MaxSize30//全局变量辅助数组大小INFINITYN65536//表示权值无限大五、算法设计1、算法分析首先，采用数据结构课程设计Prime算法构造最小生成树，Prime算法基于的存储结构为图的存储结构，由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储，那么我们就要实现邻接矩阵的初始化。然后，我们还需要自定义边所对应

5、的顶点序号以及其权值，所以就要建立一个自定义的成员函数。其次，题目要求我们输出邻接矩阵，在自定义完的各项数据的基础上，输出邻接矩阵。最后，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的最短边来扩充生成

6、树T。所以Prime算法基于的另一个存储结构就是候选最短边集：设置一个数组shortEdge[n]表示候选最短边集，数组元素包括adjvex和lowcost两个域，分别表示候选最短边的邻接点和权值。而最小代价即是最小生成树上边的权值之和。2、算法实现LinkListCreateList(void)//{//尾插法建立带头结点的通讯录链表算法LinkListhead=newListNode;//申请头结点ListNode*p,*rear;intflag=0;//结束标志置0rear=head;//尾指针初始指向头结点while(flag==0){p=

7、(ListNode*)malloc(sizeof(ListNode));//申请新结点printf("编号姓名(8)性别(2)电话(11)地址(31)");printf("--------------------------------------");scanf("%d%s%s%s%s",&(p->data.num),p->data.name,p->data.sex,p->data.phone,p->data.addr);n++;rear->next=p;//新结点连接到尾结点之后rear=p;//尾指针指向新结点printf("结束建表

8、吗？(1/0):");scanf("%d",&flag);//读入一个标志数据}rear->next=NULL;//终端结