图论论文：最小生成树算法城市高速公路问题中的应用

图论论文：最小生成树算法城市高速公路问题中的应用文档视界图论论文：最小生成树算法城市高速公路问题中的应用图论论文：最小生成树算法城市高速公路问题中的应用最小生成树在城市高速公路问题中的应用摘要：城市高速公路问题就是以最短高速路程连接一组城市的问题，在城市规划和建设中应用广泛。本文以最小生成树在城市高速公路问题中的应用为例，利用最小生成树的三种算法的分析和研究，说明了最小生成树在最优化方面的作用。关键词：城市高速公路问题Prim算法Kruskal算法简易算法一引言图论是数学的一个分支。它以图为研究对象。在图论的课程体系中，图构造是一种非常重要的非线性数据构造。带权图的最小生成树尤其被广泛应用在解决工程技术及科学管理等各个领域的最优化问题中。二背景知识1图和树：图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描绘某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是五圈连通无向图，假如树T的节点数为n，那么树的边数为n-1。2生成树：连通图G上的一个子图，该子图连通，无回路且包含图G的所有节点，称为连通图的极小连通子图。一个连通图能够有多棵不同的生成树。3最小生成树：对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因而这些生成树的各边权值之和也不一定一样，其中权值最小的生成树被称为该带权连通图的最小生成树。4高速公路问题：假设有N个城市，第i个城市的位置笛卡尔坐标为(xi，yi)，每条公路能够连接两个城市。目前原有的公路有m条，但是不能实现所有城市之间的连通，因而需要继续修建公路，在费用最低的原则下，实现N个城市的连通，还需要修建哪些条公路。由于修路的费用与公路的长短是成正比的，所以这个问题就能够转化成求修建哪几条公路能够实现所有城市的连通，同时知足所修公路总长最短。三最小生成树的求解方法构造最小生成树能够有多种算法。大多数（图论）教材中介绍了其中的两种算法Prim算法和Kruskal算法，本文另介绍一种简易算法来实现最小生成树的构造。1Prim算法思想：普里姆算法通过逐个往生成树上添加顶点来构造连通网的最小生成树。算法详细步骤：〔1〕开场：选取连通网中的任意一个顶点添加到最小生成树中。〔2〕重复执行下面操作：1〕连通网的顶点集合分成两个部分：已经添加到最小生成树中的顶点集合和尚未添加到最小生成树中的顶点集合；2〕找出所有连通这两个集合中顶点的边；3〕从中选取一条权值最小的边添加到生成树中，同时将与这条边相连的顶点也添加到生成树中。〔3〕结束：所有的顶点都被添加到最小生成树中。2Kruskal算法思想：通过逐个往生成树上添加边来构造连通网的最小生成树。算法详细步骤：〔1〕将连通网中的所有顶点添加到最小生成树中，构造一个森林；〔2〕将各边根据权值从小到大排序；〔3〕根据排好的顺序向生成树中添加不使森林中产生回路的边(若构成回路则不添加，继续考察下一条边)。直至该森林变成一棵树为止。3简易算法思想：通过逐个从连通网中删除边来构造最小生成树。算法详细步骤：〔1〕将连通网中各边根据权值从大到小排序；〔2〕根据排好的顺序从连通网中删除权值最大的边，条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留，继续删除下一条边)。直至子图中任何一条边都不能删除〔即删除任意一条边都会造成该子图不连通〕为止。4三种算法的比拟〔1〕普里姆算法：主要是对顶点进行操作；采用邻接矩阵作为存储构造，在行经过中对连通网中的每一个顶点都考察到了，因而普里姆算法的时间复杂度为()2On〔n为连通网中顶点的个数〕。普里姆算法适用于求边稠密的连通网的最小生成树。〔2〕克鲁斯卡尔算法：主要是对边进行操作，时间复杂度主要取决于对边根据权值进行排序的时间，边的个数为e，排序的时间复杂度能够做到O(eloge)，因而算法的时间复杂度为O(eloge)。克鲁斯卡尔算法适用于求边稀疏的连通网的最小生成树。〔3〕简易算法：主要是对边进行操作，时间复杂度主要取决于对边根据权值进行排序的时间，边的个数为e，排序的时间复杂度能够做到O(eloge)，因而算法的时间复杂度为O(eloge)。该算法适用于求边稀疏的连通网的最小生成树。四应用利用最小生成树来解决高速公路问题，将高速公路问题中的城市看做图中的顶点，城市之间修建的道路看做图中顶点之间的边，城市之间所修修建的公路的长度看做是图中个边上的权值。这样我们就把高速公路问题转换成了求一个有向连通网的最小生成树问题。此时假设城市个数为6，分别为a，b，c，d，e，f。并设其对应城市之间的公路距离权值及初始状态的连通无向图如下所示：文档视界图论论文：最小生成树算法城市高速公路问题中的应用图论论文：最小生成树算法城市高速公路问题中的应用typedefcharTownType;typedeffloatRoadType;typedefstruct{intn;/*图的顶点个数*/intm;/*图的边个数*/TownTypetowns[MAXVEX];/*顶点信息*/RoadTyperoads[MAXVEX][MAXVEX];/*边信息*/}GraphMatrix;typedefstruct{intstart_town,stop_town;/*边的起点和终点*/RoadTypeweight;/*边的权*/enum{EXIST,UNEXIST}ex;/*区别已经建好的公路和未修建的公路*/}Edge;Edgemst[50];2〕判定图的连通性函数判定无向图的的连通性有很多方法，这里采用的是通过对图进行深度优先搜索，统计遍历过的顶点个数，假如顶点个数比图中顶点个数少，讲明该图不连通，相反讲明该图是连通图。详细实现如下：voiddfsMatrix(GraphMatrixGM,inti,intn,int&visited[]){intj;printf“(%d〞,i);visited[i]=1;for(intj=0;j文档视界图论论文：最小生成树算法城市高速公路问题中的应用图论论文：最小生成树算法城市高速公路问题中的应用文档视界图论论文：最小生成树算法城市高速公路问题中的应用图论论文：最小生成树算法城市高速公路问题中的应用return1;}voidCreateGraph(MGraph&G){inti,j,k,w;vertexv1,v2;printf("输入无向图顶点数和边数:\n");scanf("%d%d",&G.vexnum,&G.arcnum);printf("输入各顶点的值：\n",G.vexnum);for(i=0;i0){min=c[j].lowcost;k=j;}returnk;}文档视界图论论文：最小生成树算法城市高速公路问题中的应用图论论文：最小生成树算法城市高速公路问题中的应用文档视界图论论文：最小生成树算法城市高速公路问题中的应用图论论文：最小生成树算法城市高速公路问题中的应用#include#include#defineM20#defineMAX20typedefstruct//构造边{intbegin;intend;intweight;//权值}edge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,arcnum;//顶点数和边数}MGraph;voidCreatGraph(MGraph*);//函数申明构造图voidsort(edge*,MGraph*);//函数申明对边的排序voidMiniSpanTree(MGraph*);//最小生成树intFind(int*,int);voi