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

《离散数学课外实验》 最小生成树问题 学 号 班 级 姓 名 华北电力大学数理学院 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 stdio.h #include stdlib.h #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 stdio.h #include stdlib.h #include string.h #define INFINITY 30000 /* 定义一个权值的最大值 */ #define MaxVertexNum 30 /* 图的最大顶点数为30 */ typedef struct { int arcs[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵，即边表 */ int vertexNum,edgeNum; /* 图的当前顶点数和边数 */ }MGraph; /*Graph是以以邻接矩阵存储的图类型*/ typedef struct { int adjvertex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好