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

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

学 号 班 级 姓 名

华北电力大学数理学院 2013年6月 目 录 1.问题描述 ..................................................................................................................................... 3 2.分析及设计思路 ......................................................................................................................... 3 3.结构类型定义 ............................................................................................................................. 3 4.系统功能模块介绍 .................................................................................................................... 4 5.源程序.......................................................................................................................................... 5 6.运行结果及调试分析 ................................................................................................................ 8 7.总结 .............................................................................................................................................. 9 1.问题描述 一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 1) 城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)

2.分析及设计思路

首先解决如下5个问题： （1）如何选择存储结构去建立一个带权网络。 （2）如何在所选存储结构下输出这个带权网络。 （3）如何实现Prim算法的功能。 （4）如何从每个顶点开始找到所有的最小生成树的顶点。 （5）如何输出最小生成树的边及其权值。 此问题的关键在于如何实现Prim算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。 首先我们对问题进行大致的概要分析： 这个问题主要牵涉到通过Prim的基本算法思想实现程序所要求的功能，该算法的主要思想是：假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}（u0∈V），TE={}开始，重复执行下述操作：在所有u∈U，v∈V-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 vertexs[MaxVertexNum]; /*顶点表*/ int arcs[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵，即边表 */ int vertexNum,edgeNum; /* 图的当前顶点数和边数 */ }MGraph; /*Graph是以以邻接矩阵存储的图类型*/

typedef struct { int adjvertex; /*某顶点与已构造好的部分生成树的顶点之间权值最小的顶点*/ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ }ClosEdge[MaxVertexNum]; /*用普里姆算法求最小生成树时的辅助数组 */ 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 arcs[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵，即边表 */ int vertexNum,edgeNum; /* 图的当前顶点数和边数 */ }MGraph; /*Graph是以以邻接矩阵存储的图类型*/

typedef struct { int adjvertex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */ }ClosEdge[MaxVertexNum]; /* 用普里姆算法求最小生成树时的辅助数组 */ void DisMatix(MGraph *G) { int i,j; printf("\n图的邻接矩阵：\n"); for(i=1;i<=G->vertexNum;i++) { for(j=1;j<=G->vertexNum;j++) { if(G->arcs[i][j]==INFINITY) printf(" ?"); else printf("%4d",G->arcs[i][j]);

} 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;i<=G->vertexNum;i++) for(j=1;j<=G->vertexNum;j++) G->arcs[i][j]=INFINITY; /*初始化邻接矩阵*/ printf("输入相邻两结点和其权值:\n"); for(i=1;i<=G->edgeNum;i++) {scanf("%d,%d,%d",&start,&end,&weight); /*输入边的起点和终点及权值 */ G->arcs[start][end]=weight; G->arcs[end][start]=weight; } DisMatix(G);

} void MiniSpanTree_PRIM(MGraph *G,int u ) {/* 从第u个顶点出发构造图G的最小生成树 ,最小生成树的顶点信息存放在数组closedge中*/ ClosEdge closedge; int i,j,w,k;

for(i=1;i<=G->vertexNum;i++) /*辅助数组初始化*/ if(i!=u) {closedge[i].adjvertex=u; closedge[i].lowcost=G->arcs[u][i];