prim算法建立n个城市间的最小生成树.doc

数据结构课程设计数据结构课程设计报告设计题目：n个城市连接的最小生成树专 业 通 信 工 程班 级 0903 班 学 生 彭 焱 学 号 指导教师 起止时间 2012.2.142012. 3.13 2012 年 2 学期目 录一设计题目- 3 -【问题描述】- 3 -【基本要求】- 3 -【实现提示】- 3 -二设计内容- 3 -1.分析问题及解决问题- 3 -三、基本概念- 4 -1、顺序表的基本概念- 4 -2、图的邻接矩阵的基本概念- 4 -3、最小生成树的基本概念- 5 -4.普利姆算法思想- 6 -四概要设计- 6 -1、模块作用- 6 -2、模块及模块调用关系- 6 -(1)“SeqList.h”顺序存储结构存放结点信息- 7 -(2).“AdjMGraph.h”邻接矩阵存储结构存放边的信息- 7 -(3)本课程设计中最小生成树的生成过程- 8 -五算法描述- 12 -1.流程图- 12 -六测试结果及分析- 14 -1、测试结果- 14 -2、结果分析- 16 -3、错误分析- 16 -七、心得体会和参考资料- 17 -1心得体会- 17 -2.参考资料- 17 -附录：源代码- 17 -一设计题目【问题描述】给定一个地区的n个城市间的距离网，用Prim算法或Kreskas算法建立最小生成树，并计算得到的最小生成树的代价。【基本要求】（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本上的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括那些城市间的道路，并显示得到的最小生成树的代价。（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）（3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。【实现提示】输入城市代号显示邻接矩阵执行Prim算法的到最小生成树输出最小生成树的代价二设计内容1.分析问题及解决问题按照题目要求需要采用邻接矩阵来存放城市间的距离网，且用Prim算法建立最小生成树并求最小生成树代价。将图的结点信息存放在一个顺序表中，图的边信息存储在一个二维数组edgeMaxVerticesMaxVertices中，这样就实现了用邻接矩阵存放城市间的距离网。在Prim算法的函数用两个参数，一个是图G为邻接矩阵存储结构的图；另一个是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex.三、基本概念1、顺序表的基本概念 当采用C语言描述数据结构时问题时，实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元内，这样，线性表中逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱，后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。 数组有静态数组和动态数组两种。静态数组存储空间的申请和释放有系统自动完成，动态数组存储空间的申请和释放由用户调用系统函数完成。无论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是申请的方法不同，顺序表一般采用静态数组方法实现数据元素的存储。 顺序表定义结构体如下： Typedef struct DataType listMaxsize; Int size;SeqList;其中，DataType为数组（即数据元素）的数据类型，Maxsize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size= Maxsize，SeqList是该结构体的名称。2、图的邻接矩阵的基本概念由图的定义可知，图的信息包括两部分，图中结点的信息和描述之间关系的边的信息。结点信息的描述问题，是一个简单的表存储结构问题。对于一个有n个节点的图，由于每个结点都可能与其他n-1个结点成为邻接结点，所以边之间关系的描述问题，实际上是一个n*n矩阵的计算机存储表示问题。在图的邻接矩阵存储结构中，节点信息使用一维数组存储，边的邻接矩阵使用二维数组存储，无向图的邻接矩阵一定是对称矩阵。当图中结点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中结点数目较大且边的数目远小于相同结点的完全图的边数时，采用图的邻接表存储结构效率较高。图的结构体定义如下：typedef struct SeqList Vertices; int edgeMaxVertices MaxVertices; int numOfEdges;AdjMGraph;3、最小生成树的基本概念 一个有n个结点的连通图的生成树是原图的极小连通子图，他包含原图中的所有n个结点，并且保持图连通的最少的边。 由生成树的定义可知：（1）若再生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边就会使生成树中存在回路而不再满足生成树的定义；（3）一个连通图的生成树可能得到不同的生成树。使用不同的寻找方法可以得到不同的生成树。另外，从不同的初始结点出发也可以得到不同的生成树。 从生成树的定义显然可以证明，对于有n个结点的无向连通图，无论他的生成树的形状如何，一定有且只有n-1条边。 如果无向连通图是一条带权图，那么他的所有生成树中必有一颗边的权值总和为最小的生成树，称这棵生成树为最小代价生成树，简称最小生成树。 从最小生成树的定义可知，构造有n个结点的无向连通带权图的最小生成树必须满足以下三点：（1）构造的最小生成树必须包括n个结点（2）构造的最小生成树中有且只有n-1条边（3）构造的最小生成树中不存在回路构造最小生成树的方法有许多种，典型的构造方法有两种，一种称作普利姆算法，另一种叫做克鲁斯卡尔算法。 4.普利姆算法思想假设G=(V,E)为一个带权图，其中V为带权图中结点的集合，E为带权图中的边的权值集合。设置两个信新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。普利姆算法思想是：令集合U的初值为Uu0（即假设构造最小生成树时从结点u0开始），集合T 的初值为T=。从所有结点u属于U和结点v属于V但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。此时集合U中存在着最小生成树的结点，集合T中存放着最小生成树边的权值集合。四概要设计1、模块作用头文件用来存放邻接矩阵存储结构定义以及相应的图的操作函数与图的创建及普里姆函数的设计。主函数“prim.cpp”来测试程序2、模块及模块调用关系AdjMGraph.h(1)“SeqList.h”顺序存储结构存放结点信息a.初始化ListInitiate(L)：初始化线性表L。b.求当前数据元素个数ListLength（L）：函数返回线性表L的当前数据元素的个数c.插入数据元素ListInsert(L,i,x)：在现象表L的第i个数据前插入数据元素x，如果插入成功返回1，插入失败返回0。其约束条件为0iListLength（L），即若i=0，表示在第一个元素之前插入数据元素x，若i= ListLength（L）-1，表示在最后一个元素前插入数据元素x，若i= ListLength（L），表示在最后一个元素之后插入数据元素x。d.删除数据元素ListDelete(L,i,x)：删除线性表L的第i个元素，所删除的数据元素由输出参数x带回。如果删除成功返回1，删除失败返回0，其约束条件为0iListLength（L）-1，若i=0，表示删除第一个数据元素，若i= ListLength（L）-1，表示删除最后一个数据元素。e.取数据元素ListGet(L,i,x)：取线性表L的第i个数据元素，所取得数据元素由输出参数x带回，取元素成功返回1，取元素失败返回0。其约束条件为 0iListLength（L）-1，若i=0，表示取第一个数据元素，若i= ListLength（L）-1，表示取最后一个数据元素。(2).“AdjMGraph.h”邻接矩阵存储结构存放边的信息a. 初始化图G，n为结点个数。 Initiate(AdjMGraph *G, int n)b. 在图G中插入结点vertex InsertVertex(AdjMGraph *G, DataType vertex)c. 在图G中插入边，边的权值为weightInsertEdge(AdjMGraph *G, int v1,int v2,int weight) d. 在图G中删除边DeleteEdge(AdjMGraph *G,int v1,int v2) e. 删除图G中的结点v以及与该节点相关的所有边DeleteVerten(AdjMGraph *G,int v) f. 在图G中寻找序号为v的结点的第一个邻接结点GetFirstVex(AdjMGraph G,int v) g.在图G中寻找v1结点的邻接结点v2的下一个邻接结点.GetNextVex(AdjMGraph G,int v1,int v2)(3)本课程设计中最小生成树的生成过程 下图中给出了用普利姆算法构造最小生成树的过程。(a)为一个有7个结点10条边的无向边的带权图。初始集合U=A，集合VU=B，C，D，E，F，G，T=，如图（b）所示，此时，存在两条一个结点在U、另一个结点在集合VU中的边，具有最小权值的边（A，B），权值为50，把结点B从VU加入到集合U中，把边（A，B）加入到T中，如图（c）所示，在所有以u为集合U中结点、v为集合VU中结点的边（u，v）中寻找具有最小权值的边（u，v），寻找到的是（B,E），权值为40，把结点E从集合VU中加入到集合U中，把边（B,E）加入到T中，如图（d）所示，随后依次从集合VU加入到集合U中的结点为D，F，G，C，依次加入到T中的边为（E，D），权值为50，（D,F）权值为30，（D,G），权值为42，（G，C），权值为45，分别如图（e）（f）（g）（h）所示，最后得到的图（h）就是从A结点出发构造的最小生成树。 (a) (b) (c) (d) (e) (f) (g) (h) 设计说明：（1）函数中定义一个临时数组lowcost，数组元素lowcostv中保存了集合中结点ui与集合VU中结点uj的所有边中当前具有最小权值的边（u，v）。 （2）集合U的初值为U=序号为j的结点。Lowcost的初始值为邻接矩阵数组中第j行的值，这样初始时lowcost中就存放了从集合U中的结点j到VU中各节点的权值。（3）每次从lowcost中寻找具有最小权值的边，根据lowcost的定义，这样的边其弧头结点必然为集合U中的结点，其弧尾结点必然为集合VU中的结点，当选到这样的边（u，v）时，就保存其结点数据和权值数据到参数closevertex中，并将lowcostv置为-1，表示点v加入到了集合U中。（4）当节点v从集合VU加入到集合U后，若存在一条边（u，v），u是集合U的结点，v是集合VU的节点，且边（u，v）较原先lowcostv的权值更小，则用这样的权值修改原先lowcostv中相应权值。（5）以图（a）所示的带权图为例，调用普利姆函数时数组lowcost的动态变化过程如下所示。其中第一图表示初始结点0在集合U中，结点0到其他结点有两条边，权值分别为50和60；第二图表示结点1加入到集合U中，结点1加入集合U后，因结点1到结点3存在一条权值为65的边，该权值小于原先的无穷大，所以需要把，lowcost3改为65，因结点1到结点4存在一条权值为40的边，该权值小于原先的无穷大，所以需要把lowcost4改为40，第三图表示结点4加入到集合U后的状态，第四图表示结点3加入集合u后的状态，第五图表示结点5加入到集合U后的状态，第六图表示结点6加入到集合U后的状态，最后一图表示结点3加入到集合U后的状态。 lowcost lowcost lowcost lowcost lowcost lowcost lowcost 五算法描述1.流程图创建用邻接矩阵表示的城市道路网输入城市属N=7道路数e=20输入城市a输入表示两个城市间距离RowColWeight rcw返回 图1 创建邻接矩阵流程图判断程序是否为真Prim算法用铺助数组lowCost输入初始城市序号jfor(i=1;isize=0;int ListLength(SeqList L)return L.size;int ListInsert(SeqList *L,int i,DataType x)int j;if(L-size=MaxSize)printf(顺序表已满无法插入！n);return 0;else if(iL-size)printf(参数i不合法！n);return 0;else for(j=L-size;ji;j-) L-listj=L-listj-1; L-listi=x; L-size+; return 1;int ListDelete(SeqList *L,int i,DataType*x)int j;if(L-size=0)printf(顺序表已空无数据可删！n);return 0;else if(iL-size-1)printf(参数i不合法！n);return 0;else*x=L-listi;for(j=i;jsize;j+) L-listj=L-listj+1; L-size-; return 1; int ListGet(SeqList L,int i,char*x) if(iL.size-1)printf(参数i不合法！n);return 0; else *x=L.listi; return 1; typedef structSeqList Vertices; /* 存放结点的顺序表 */int edgeMaxVerticesMaxVertices; /* 存放边的邻结矩阵地 */int numOfEdges; /* 边的条数 */AdjMGraph; /* 图的结构体定义 */void Initiate(AdjMGraph *G, int n) /* 初始化 */int i,j;for(i=0;in;i+)for(j=0;jedgeij=0;else G-edgeij=MaxWeight;G-numOfEdges=0; /* 边的条数置为0 */ListInitiate(&G-Vertices); /*顺序表初始化 */void InsertVertex(AdjMGraph *G, DataType vertex) /* v在图G中插入结点vertex */ListInsert(&G-Vertices, G-Vertices.size,vertex); /* 顺序表尾插入 */void InsertEdge(AdjMGraph *G, int v1,int v2,int weight) /*在图G中插入边，边的权为weight */if(v1G-Vertices.size | v2G-Vertices.size|v2edgev1v2=weight;G-numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2)/*在图G中删除边 */if(v1G-Vertices.size | v2G-Vertices.size | v1=v2)printf(掺数v1或v2越界出错! n);exit(1);if(G-edgev1v2=MaxWeight | v1=v2)printf(该边不存在!n);exit(0);G-edgev1v2=MaxWeight;G-numOfEdges-;void DeleteVertex(AdjMGraph *G,int v) /*删除结点V*/int n=ListLength(G-Vertices),i,j;DataType x;for(i=0;in;i+) /*计算删除后的边数*/for(j=0;jedgeij0 & G-edgeijnumOfEdges-; /*计算被删除边*/for(i=v;in;i+) /*删除第v行*/for(j=0;jedgeij=G-edgei+1j;for(i=0;in;i+) /*删除第v列*/for(j=v;jedgeij=G-edgeij+1;ListDelete(&G-Vertices,v,&x);int GetFirstVex(AdjMGraph G,int v)/*在图G中寻找序号为v的结点的第一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/int col;if(vG.Vertices.size)printf(参数v1越界出错!n);exit(1);for(col=0;col0 & G.edgevcolMaxWeight) return col;return -1;int GetNextVex(AdjMGraph G,int v1,int v2)/*在图G中寻找v1结点的邻接结点v2的下一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/*v1和v2都是相应结点的序号*/ int col; if(v1G.Vertices.size | v2G.Vertices.size) printf(参数v1或v2越界出错!n); exit(1); for(col=v2+1;col0 & G.edgev1colMaxWeight) return col; return -1;typedef structint row; /*行下标*/int col; /*列下标*/int weight; /*权值*/RowColWeight; /*边信息结构体定义*/void CreatGraph(AdjMGraph *G,char V,int n,RowColWeight E,int e)/*在图G中插入v个结点信息V和e条边信息E*/int i,k;Initiate(G,n); /*结点顺序表初始化*/for(i=0;in;i+)InsertVertex(G,Vi); /*结点插入*/for(k=0;ke;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight); /*边插入*/typedef structVerT vertex;int weight;MinSpanTree;void Prim(AdjMGraph G, MinSpanTree closeVertex)/*用普里姆算法建立带权图G的最小生成树closeVertex*/VerT x;int n=G.Vertices.size,minCost;int *lowCost=(int *)malloc(sizeof(int)*n);int i,j,k; printf(请输入第一个城市:); scanf(%d,&j);for(i=0;in;i+) /*初始化*/ lowCosti=G.edgeji; /*从结点j出发构造最小生成树*/ ListGet(G.Vertices,j,&x); /*取结点j*/ closeVertexj.vertex=x; /*保存结点j*/ lowCostj=-1; /*标记结点j*/ for(i=1;in;i+)/*结点寻找当前最小权值的边所对应的弧头K*/minCost=MaxWeight;for(j=0;jn;j+) if(lowCostj0) minCost=lowCostj; k=j;ListGet(G.Vertices,k,&x); /*取弧头结点K*/closeVertexi.vertex=x; /*保存弧头结点K*/closeVertexi.weight=minCost; /*保存相应的权值*/lowCostk=-1; /*标记结点K*/*根据加入集合U的结点K修改lowCost中的数值*/for(j=0;jn;j+)if(G.edgekjlowCostj)lowCostj=G.edgekj;主文件：prim.cpp#include#include#includetypedef char VerT;#define MaxSize 100 #define MaxVertices 10#define MaxWeight 10000#define