图论 最小生成树在城市交通建设中的应用

最小生成树在城市交通建设中的应用姓名XX学号S100203029专业计算机应用技术2010年12月4A目录摘要.......................................................................................................................I绪论.........................................................................................................................12有关最小生成树的概念.....................................................................................23prim算法介绍.....................................................................................................34系统设计及其应用.............................................................................................5一、系统设计..................................................................................................5二、最小生成树应用......................................................................................65总结.....................................................................................................................9参考文献...............................................................................................................10附件：...................................................................................................................11I最小生成树在城市交通建设中的应用摘要连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在MicrosoftVisualC++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。关键字：PRIM算法、最小生成树、邻接矩阵、交通建设1绪论中国国际工程咨询公司交通业务部主任周晓勤指出，“以前的各专业规划主要是按照本行业交通发展的需求进行研究和规划的，在交通设施总量不足、基本网不完善的时候，互相之间的矛盾并不突出。但随着多种运输方式设施建设的快速发展，各行业交通网络的逐步完善，多种运输方式网络之间的叠加，难免显现出各种运输方式在通道和枢纽衔接上的不协调。其结果是，资源浪费，效率低下，使用不便利。而综合交通网发展规划的颁布有利于运输整体结构的调整，资源节约和集约利用，对于交通运输业的可持续发展具有重要和深远的意义。”在社会主义建设时期，各个城市建设问题尤其是交通建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设公路，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。各个农村交通建设好之后，则可再根据将农村作为一个结点和其它农村再次运用最小生成树。最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干条高速公路，把n个城市联系在一起。普里姆算法通过寻找无向图中权值最小的边，并且将其组合成最小生成树，同时将最小生成树以点集的形式输出，便于观察。根据课程设计任务书要求，本系统开发主要完成以下功能和性能。(1)输入无向图的方式要尽量简单方便。(2)要能够形象方便的观察无向图的结构。(3)要能够形象地演示PRIM算法求最小生成树的过程。本文第二章主要介绍图和最小生成树、邻接矩阵等概念。第三章主要介绍prim算法。第四章进行系统设计与调试及其在交通建设中的应用。22有关最小生成树的概念最小生成树：连通加权图里权和最小的生成树称为最小生成树。从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。定义一（图）：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：G=(V,E)V={iV|jVVertexType}E={iV,jV|iV,jV∈V∧P(iV,jV)}其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，VertexType是用于描述顶点类型，集合E中P(iV,jV)的含义是：对有向图来说用“”表示，对无向图来说用“（）”表示，即从iV到jV两个顶点之间存在边。定义二（树）：树包含n（n=0）个节点。当n=0时表示为空树。其定义如下：T=(D,R)其中，D为树中节点的有限集合，关系R满足一下条件：1）有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点。2）除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。3）D中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和n（n=0）个子结点。图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，用来存放顶点的信息和边或弧的信息。定义三（邻接矩阵（AdjacencyMatrix））：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：（本文主要为无向图的邻接矩阵）（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（1）无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。定义四（生成树）：如果T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。33prim算法介绍最小生成树的两个著名算法：prim算法[和克鲁斯卡尔算法[2],本文应用的是prim算法。则克鲁斯卡尔算法则不进行描述了。Prim算法的基本思想：首先，选择带最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。PRIM算法介绍：设图中顶点的全集为V,U中存放已选中过的点,用数据结构closedge[]存放选择需要的数据,先把下标0对应点放入U中,closedge[i].uxiabiao=0,(因为U中只有下标0这一个点),closedge[i].lowcost中存放其他点到下标为0的点的权,closedge[0].lowcost=0;表示下标为0的点已在U中了。在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min，用擂台式比较法选出closedge[j].lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。输出选中的这条边，它是最小生成树中的一条边。因为U中又加入了一个点，所以要修改closedge[i].lowcost的值，比较新选中点与V-U中点的权和原来的closedge[i].lowcost,取小的那个存入。然后继续如上的选择,循环vexnum-1次,就选出了最小生成树中的vexnum-1条边。本程序采用数组存储结构进行存储，把第一个点所到的边记录下来，然后把权值最小的边存入数组，同时将刚才所存边的的终点作为起点再次记录该点所到的边，并记录权值最小的边存入数组，这个过程中，已经被访问的点不再访问。知道最后所有的权值最小的边全部输出。这就是PRIM算法求最小生成树。Prim算法有两种形式，其伪代码如下：算法一：procedurePrim;beginT:=Φ；U:={1};whileUVdobegin(u,v):=u∈U且v∈V-U的最小权边;T:=T∪{(u,v)};U:=U∪{v};end;end;改进的prim算法2如下：procedurePrim(varG:adj_matrix;size:integer);{G为图，size为图的节点数目;注意：假设输入的图是连通图}varlowcost:array[1..maxsize]ofinteger;used:array[1..maxsize]ofboolean;closeset:array[1..maxsize]ofinteger;i,j,k,min:integer;beginfori:=2tosizedo{初始化，此时U只含有顶点1}4beginlowcost[i]:=G[1,i];closeset[i]:=1;used[i]:=false;end;used[1]:=true;fori:=2tosizedobeginmin:=maxint;j:=i;fork:=2tosizedo{用选择法寻找顶点分别在V-U与U中权最小的边}if(notused[k])and(lowcost[k]beginmin:=lowcost[k];j:=k;end;writeln(fout,'(',closeset[j],',',j,')');{输出找到的最小生成树的一条边，此处可根据情况修改}used[j]:=true;{将j填加到U}fork:=2tosizedo{调整lowcost和closeset}if(notused[k])and(G[j,k]beginlowcost[k]:=G[j,k];closeset[k]:=j;end;end;end;54系统设计及其应用一、系统设计数据信息以结构体【3】【4】和数组形式储存，结点的信息结构体定义如下：structgraph{chartnode;charhnode;doublequanzhi;}gr[100];charnode[50]=;图的存储结构为：#defineINFINITYINT_MAX//最大值#defineMAX_VERTEX_NUM20//最多的顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图、有向网、无向图、无向网}typedefstructArcCell{VRTypeadj;//顶点关系类型：图：0、1网：权值InfoType*info;//该弧相关信息指针}ArcCell,AdjMaTrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//