文档介绍：XXXX研究生堂下考试答卷
2012-2013学年第 1 学期
2012年 12 月 18 日
最小生成树在城市高速公路问题中的应用
摘要: 城市高速公路问题就是以最短高速路程连接一组城市的问题,在城市规划和建设中应用广泛。本文以最小生成树在城市高速公路问题中的应用为例,利用最小生成树的三种算法的分析和研究,阐明了最小生成树在最优化方面的作用。
关键词:城市高速公路问题 Prim算法 Kruskal算法简易算法
一引言
图论是数学的一个分支。它以图为研究对象。在图论的课程体系中,图结构是一种非常重要的非线性数据结构。带权图的最小生成树尤其被广泛应用在解决工程技术及科学管理等各个领域的最优化问题中。
二背景知识
1 图和树:图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。树是五圈连通无向图,如果树T的节点数为n,那么树的边数为n-1。
2 生成树:连通图 G 上的一个子图,该子图连通,无回路且包含图G 的所有节点,称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。
3 最小生成树:对一个带权连通图,也有多可不同的生成树。由于该图是带权图,各边的权值不一定相等,因此这些生成树的各边权值之和也不一定相同,其中权值最小的生成树被称为该带权连通图的最小生成树。
4 高速公路问题:假设有 N 个城市,第 i 个城市的位置笛卡尔坐标为(xi,yi),每条公路可以连接两个城市。目前原有的公路有m 条,但是不能实现所有城市之间的连通,因此需要继续修建公路,在费用最低的原则下,实现 N 个城市的连通,还需要修建哪些条公路。由于修路的费用与公路的长短是成正比的,所以这个问题就可以转化成求修建哪几条公路能够实现所有城市的连通,同时满足所修公路总长最短。
三最小生成树的求解方法
构造最小生成树可以有多种算法。大多数《图论》教材中介绍了其中的两种算法 Prim 算法和 Kruskal 算法,本文另介绍一种简易算法来实现最小生成树的构造。
1 Prim 算法
思想:普里姆算法通过逐个往生成树上添加顶点来构造连通网的最小生成树。
算法具体步骤:
(1) 开始:选取连通网中的任意一个顶点添加到最小生成树中。
(2) 重复执行以下操作:
1) 连通网的顶点集合分成两个部分:已经添加到最小生成树中的顶点集合和尚未添加到最小生成树中的顶点集合;
2) 找出所有连通这两个集合中顶点的边;
3) 从中选取一条权值最小的边添加到生成树中,同时将与这条边相连的顶点也添加到生成树中。
(3)结束:所有的顶点都被添加到最小生成树中。
2 Kruskal 算法
思想:通过逐个往生成树上添加边来构造连通网的最小生成树。
算法具体步骤:
(1) 将连通网中的所有顶点添加到最小生成树中,构造一个森林;
(2) 将各边按照权值从小到大排序;
(3) 按照排好的顺序向生成树中添加不使森林中产生回路的边(若构成回路则不添加,继续考察下一条边)。直至该森林变成一棵树为止。
3 简易算法
思想:通过逐个从连通网中删除边来构造最小生成树。
算法具体步骤:
(1) 将连通网中各边按照权值从大到小排序;
(2) 按照排好的顺序从连通网中删除权值最大的边,条件是使删除该边后的子图仍然保持连通(若删除后子图不连通则改边保留,继续删除下一条边)。直至子图中任何一条边都不能删除(即删除任意一条边都会造成该子图不连通)为止。
4 三种算法的比较
(1) 普里姆算法:主要是对顶点进行操作;采用邻接矩阵作为存储结构,在行过程中对连通网中的每一个顶点都考察到了,因此普里姆算法的时间复杂度为(n 为连通网中顶点的个数)。普里姆算法适用于求边稠密的连通网的最小生成树。
(2) 克鲁斯卡尔算法:主要是对边进行操作,时间复杂度主要取决于对边按照权值进行排序的时间,边的个数为e,排序的时间复杂度可以做到O (eloge),因此算法的时间复杂度为 O(eloge)。克鲁斯卡尔算法适用于求边稀疏的连通网的最小生成树。
(3) 简易算法:主要是对边进行操作,时间复杂度主要取决于对边按照权值进行排序的时间,边的个数为e,排序的时间复杂度可以做到 O (eloge),因此算法的时间复杂度为 O(eloge)。该算法适用于求边稀疏的连通网的最小生成树。
四应用
利用最小生成树来解决高速公路问题,将高速公路问题中的城市看做图中的顶点,城市之间修建的道路看做图中顶点之间的边,城市之间所修修建的公路的长度看做是图中个边上的权值。这样我们就把高速公路问题转换成了求一个有向连通网的最小生成树问题。此时假设城市个数为6,分别为a,b,c,d,e,f。