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

离散数学课外实验最小生成树问题学 号班 级姓 名华北电力大学数理学院2013年6月目 录1.问题描述32.分析及设计思路33.结构类型定义34.系统功能模块介绍45.源程序56.运行结果及调试分析87.总结91.问题描述一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1) 城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边) 2.分析及设计思路 首先解决如下5个问题：（1）如何选择存储结构去建立一个带权网络。（2）如何在所选存储结构下输出这个带权网络。（3）如何实现Prim算法的功能。（4）如何从每个顶点开始找到所有的最小生成树的顶点。（5）如何输出最小生成树的边及其权值。此问题的关键在于如何实现Prim算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。首先我们对问题进行大致的概要分析：这个问题主要牵涉到通过Prim的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0（u0V），TE=开始，重复执行下述操作：在所有uU，vV-U的边（u,v）E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，E）为N的最小生成树。问题的输入数据的格式为：首先提示输入带权网络的顶点边数，我定义的为整形数据型，然后输入每一条边的信息，即边的两个顶点以及权值，是十进制整数类型，这样我们就建立了一个带权网络，并用邻接矩阵来存储，生成一个方阵显示出来。问题的输出数据格式为：输出是以邻接矩阵存储结构下的方阵，以及从不同顶点开始的最小生成树。达到目标：用Prim算法实现任意给定的网和顶点的所有最小生成树，并且输出各边的权值。3.结构类型定义#include #include #define INFINITY 30000 /* 定义一个权值的最大值 */#define MaxVertexNum 30 /* 图的最大顶点数为30 */typedef struct /int vertexsMaxVertexNum; /*顶点表*/ int arcsMaxVertexNumMaxVertexNum; /* 邻接矩阵，即边表 */ int vertexNum,edgeNum; /* 图的当前顶点数和边数 */MGraph; /*Graph是以以邻接矩阵存储的图类型*/typedef struct int adjvertex; /*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ClosEdgeMaxVertexNum; /*用普里姆算法求最小生成树时的辅助数组 */4.系统功能模块介绍输出矩阵存储的形式：（城市间无路径用？代替，如图）void DisMatix(MGraph *G)创建图：void CreatGraph(MGraph *G)PRiM求最小生成树：void MiniSpanTree_PRIM(MGraph *G,int u )主函数：int main()5.源程序#include #include #include #define INFINITY 30000 /* 定义一个权值的最大值 */#define MaxVertexNum 30 /* 图的最大顶点数为30 */typedef struct int arcsMaxVertexNumMaxVertexNum; /* 邻接矩阵，即边表 */ int vertexNum,edgeNum; /* 图的当前顶点数和边数 */MGraph; /*Graph是以以邻接矩阵存储的图类型*/typedef struct int adjvertex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ClosEdgeMaxVertexNum; /* 用普里姆算法求最小生成树时的辅助数组 */void DisMatix(MGraph *G) int i,j; printf(n图的邻接矩阵：n); for(i=1;ivertexNum;i+) for(j=1;jvertexNum;j+) if(G-arcsij=INFINITY) printf( ?); else printf(%4d,G-arcsij); printf(n); printf(n); void CreatGraph(MGraph *G)/* 构造邻接矩阵结构的图G */ int i,j; int start,end,weight; printf(请输入图的顶点数和边数:); scanf(%d,%d,&G-vertexNum,&G-edgeNum); /*输入图的顶点数和边数 */ for(i=1;ivertexNum;i+) for(j=1;jvertexNum;j+) G-arcsij=INFINITY; /*初始化邻接矩阵*/ printf(输入相邻两结点和其权值:n); for(i=1;iedgeNum;i+) scanf(%d,%d,%d,&start,&end,&weight); /*输入边的起点和终点及权值 */ G-arcsstartend=weight; G-arcsendstart=weight; DisMatix(G);void MiniSpanTree_PRIM(MGraph *G,int u )/* 从第u个顶点出发构造图G的最小生成树 ,最小生成树的顶点信息存放在数组closedge中*/ ClosEdge closedge; int i,j,w,k; for(i=1;ivertexNum;i+) /*辅助数组初始化*/ if(i!=u) closedgei.adjvertex=u; closedgei.lowcost=G-arcsui; closedgeu.lowcost=0; /* 初始，U=u */ for(i=1;ivertexNum-1;i+) /*选择其余的G-vexnum-1个顶点 */ w=INFINITY; for(j=0;ivertexNum;j+) /* 在辅助数组closedge中选择权值最小的顶点 */ if(closedgej.lowcost!=0&closedgej.lowcostw) w=closedgej.lowcost; k=j; /* 求出生成树的下一个顶点k*/ closedgek.lowcost=0; /* 第k个顶点并入U集*/ for(j=1;jvertexNum;j+) /* 新顶点并入U后，修改辅助数组*/ if(G-arcskjarcskj; printf(打印最小代价生成树的各条边：n); for(i=1;ivertexNum;i+) /*打印最小生成树的各条边 */ if(i!=u) printf(%d-%d,%dn,i, closedgei.adjvertex, G-arcsiclosedgei.adjvertex); int main() printf(构造n个城市连接的最小生成树问题nn); printf(1.输入城市的个数和城市间的路径数。n); printf(2.输入相邻城市名字及他们之间的路径长度。n); printf(3.以邻接矩阵存储各个城市间的信息并输出。n); printf(4.用Prim算法得出n个城市连接的最小生成树。n); printf(5.打印出n个城市连接的最小生成树路径。nn); MGraph G; /*采用邻接矩阵结构的图*/ int v; CreatGraph(&G); /*生成邻接矩阵结构的图*/ printf(从哪一个顶点开始:); scanf(%d,&v); /*输入Prim算法中的起始顶点*/ MiniSpanTree_PRIM(&G,v); /*Prim算法求最小生成树*/ return 0;6.运行结果及调试分析 对于任意给定的网和起点，用Prim算法的基本思想求解出所有的最小生成树并输出这些边的权值，所以如何实现输出显示所有的最小生成树关键问题所在，经过分析调试，用一个for语句就可以解决这个问题，从每个顶点出发，开始每一次遍历并输出显示出来。算法的时间和空间性能分析：根据程序中算法的循环语句可以判断出Prim算法的时间复杂度为O（n2）算法和图中的边数无关。因此Prim算法适合求稠密网的最小生成树，因为在算法中用邻接矩阵的存储结构，在无向图中，邻接矩阵是对称的。所以仅需要存储上三角或下三角的元素，因此需要n(n+1)的存储空间。7.总结最小生成树主要由Prim算法完成，由于老师平时课上对普利姆算法的知识的透彻讲解，通过整体构思，于是，先确立了基本步骤：1.建立一个具有n个定点的无向图；2.接着创建一个邻接矩阵来存储该图，然后初始化该矩阵；3.最后根据Prim算法，得到了最小生成树以及各边的权值。皇天不负有心人，按照步骤，忙碌了两周，在不断地努力下，总算将此程序设计出来。尽管不完全是自己独立完成，但仍然很欣慰，因为在设计的过程中，让我了解到要设计一个大型程序，查