《离散数学课外实验--最小生成树问题(1)》

《《离散数学课外实验--最小生成树问题(1)》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《离散数学课外实验》学班级姓名华杜电力大嗲叙理嗲呢2013年6用目录1.32.分析及设计思路33.结构类型定义34.系统功能模块介绍45.、源餅56.运行结果及调试分析87.，雑91.问题描述一个地

2、X:的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1)城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)2.分析及

3、设计思路首先解决如下5个问题：(1)如何选择存储结构去建立一个带权网络。(2)如何在所选存储结构下输出这个带权网络。(3)如何实现Prim算法的功能。(4)如何从每个顶点开始找到所有的最小生成树的顶点。(5)如何输出最小生成树的边及其权值。此问题的关键在于如何实现Prim算法，实现的过程屮如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。首先我们对问题进行大致的概要分析：这个问题主要牵涉到通过Prim的基本算法思想实现程序所要求的功能,该算法的主要思想是：假设N=(V,{E})是连通网，TE是N上最小生成树屮边的集合

4、。算法从U={u0}(uOEV),TE={}开始，重复执行下述操作：在戶斤冇uEU，vEV-U的边(u，v)EE中找一条代价最小的边(uO,vO)并入集合TE,同时vO并入U,直至U=V为止。此时TE屮必有n-1条边，则T=(V,{E})为N的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立了一个带权网络，并用邻接矩阵來存储，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始的最小生成树。达

5、到目标：用Prim算法实现任意给定的网和顶点的所冇最小生成树，并且输出各边的权值。3.结构类型定义^include^include〈stdlib.h〉#dcfineINFINITY30000A定义一个权值的最大值*/#dcfincMaxVertexNum30A图的最大顶点数为30*/typedcfstruct{//intvcrtcxs[MaxVertcxNum];/*顶；^表本/intarcs[MaxVertcxNum][MaxVertcxNum];/*邻接矩阵，即边表*/intvertexNum,edgeNum;/*图的当前顶点数和边

6、数*/}MGraph;AGraph是以以邻接矩阵存储的图类型*/typedcfstruct{intadjvcrtcx;/*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}ClosEdgc[MaxVertcxNum];/*用普里姆算法求最小生成树时的辅助数组V1.系统功能模块介绍?•5s?????•2??•5?:45输出矩阵存储的形式：(城市间无路径用？代替，如图)voidDisMatix(MGraph*G)创建图：voidCrcatGraph(MGraph氺G)PRiM

7、求最小生成树：voidMiniSpanTrce_PRIM(MGraph*G,intu)主函数：intmain()2.源程序^include〈stdio.h>^include^include〈string.h>#defineINFINITY30000A定义一个权值的最大值*/#defineMaxVertexNum30/*图的最大顶点数为30*/typedefstruct{intarcs[MaxVertexNum][MaxVertexNum];/*邻接矩阵，即边表*/intvertexNum,edgeNum;/*图的当前顶点数和边数*/}M

8、Graph;/*Graph是以以邻接矩陈存储的图类型*/typedefstruct{intadjvertex;/*茶顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/intlowcost;/*某顶点与已构造好的部分生成树的顶点之间的最小权值*/}ClosEdge[MaxVertexNum];A用普里姆算法求最小生成树时的辅助数组VvoidDisMatix(MGraph*G){inti,j;printf(〃图的邻接矩阵：〃)；for(i=l;i〈二G->vertexNum;i++){for(j二1;j<=G->vertexNum;j++){if(

9、G->arcs[i][j]==INFINITY)printf(〃？