皖江城市带交通干线布局研究——基于图论最小生成树Kruskal算法

时间：2025-03-09

皖江城市带交通干线布局研究——基于图论最小生成树Kruskal算法

第 2卷第 1 5 2期21年 1 00 2月

乐山师范学院学报J u n o e h n T a h r olg o r￣ fL s a e c e s C l e e

Vo -5. . 2 l2 No 1De .01 c2 0

皖江城市带交通干线布局研究——

基于图论最小生成树 K ukl法 rsa算方叶林毛玲玲，

(.徽大学商学院， 1安安徽合肥 20 3;.州大学经济学院，州贵阳 5 02 ) 3 09 2贵贵 5 05

摘

要：随着《皖江城市带承接产业转移示范区规划》的进一步实施，如何设计一条科学合理的交通干线成为关键所

在。文章从计算机学科图论的角度人手，利用 K uk rsM求解最小生成树算法，对构建最小投资的皖江城市带快速干线进行研究。首先用无向图的概念对皖江城市带主要城市及其距离进行图的抽象，然后给出算法过程及其实质求解意义并得出结

论最后论述了该算法的不足并对算法的结论进行修正。本文的结论可作为皖江城市带未来立体交通布局的参考。关键词：皖江城市带；交通干线； rsa算法 K ukl中图分类号：5 0 F9文献标识码： A文章编号：0 9 8 6 (0 0 1— 0 5 0 10— 6 6 2 1 )2 0 3— 4

皖江城市带主要的城市成员包括合肥、湖、芜马鞍山、陵、庆、州、湖、州、铜安池巢滁宣城、市九全境和六安市的舒城县、安区， 5金共 9个县 (、市

局的实证性研究较少。本文选取一个新的视角，即从计算机学科图论 K ukl法的角度，皖江城 rsa算对市带交通干线的布局进行实证性研究。

区)。之前有部分学者对皖江城市带的空间结构[ 1 j及交通布局进行了研究：陈明星，良松(05认查 20 )为皖江经济带城市体系有两个特征，一是人口分布低水平均衡，是体系内部空间关联性弱嘲李二，恕宏 (0 6认为皖江城市带基本骨架表现为“ 20)十字架型”构，一条主线和一条副线“结由串珠”而成，并提出“主一副二辅”一的皖江“型”镇空鹰城

1问题的抽象和说明从计算机学科的角度来看，在现实世界的若干事物或社会的若干现象之间均存在着某种联系。于皖江城市带交通干线问题，以用实心小对可圆圈表示城市，

用边

表示城市之间联通的道路，上的权表边示两地间距离的公里数，络网的构成可采用

间布局模式例吴威，,曹有挥，曹卫东等(0 7以安 20 )徽沿江为实证，采用加权平均旅行时间指标，分析了高速公路网构建对节点区内联系及区外联系可达性格局的影响，也有学者对中部地区城市带做出比较研究，出皖江城市带的优劣势阁得。总体而

言，大部分学者侧重于皖江城市带的发展战略研究，属于理论层次上的论述，对皖江城市带交通布

“一”接来点点邻描述嘲。皖江城图 1皖江城市带十城市的地理位置

收稿日期：0 0 0— 3 2 1— 9 0

作者简介：方叶林( 9 6 )男， 18一，安徽巢湖人，安徽大学商学院 2 0旅游管理专业硕士研究生，究方向： 08研旅游管理与规划。 ‘ 3 5

皖江城市带交通干线布局研究——基于图论最小生成树Kruskal算法

市带十个城市合肥、芜湖、马鞍山、铜陵、安庆、池州、巢湖、州、城、安①滁宣六的地理位置如下图所示( 1,图 )在本文中分别用大些字母 A、 C、 E B、 D、、F G、 IJ、 H、、表示。

是在 G中求最小生成树的 Kukl rsa算法主要步骤如下：

() 1选择一条边 W e)使 w(尽可能小； (, e) ( )边 e,…,i经选好，从 E e, 2若 e, e已则{ e, …

2理想状态下十个城市之间的空间距离我们可以根据每个城市的经纬度推算出他们之间大概的距离，借助互联网工具可以很快查出1 0个城市的经纬度，同时根据各地的经纬度计算出他们之间的距离【 7 j无向图角度来看，。从皖江城市带共有 1城市，即一共有 C 0= 0 ( 0个 12 1 2 1/ 1

…

e中依照下歹原则选取 e 1使得：)[ e i} l j i。+ 1G{,, e e 1]回路；) i】+无 2在满足 1的条件下使 w e 1 ) (i )+

尽可能小。中 e其 i为边；(i w e为边 e的相应权数； ) i E为边的集合。( ) 2不能进行时， 3当( )过程停止。一

、

用这种算法对图 2进行推算，最终可以求得条权数最小的干线连接十个城市，使得总路程

8= 5个距离。于是得到理想状态下皖江城市 4 1)带 1 O城市的距离如下表所示 ( 1。表 )

表 1理想状态下皖江城市带十城市之间的距离 k m

最小，符合节约费用的原则。该算法的实质过程是：在无向图中，按照边的权数从小到大依次排序，从而获得边的权值递增序列，进而在图中依次递增序列选择边的集合。如果新选择边与已经确认的边构成回路，放弃该边，则继续选择权递增的边序列中的下一条边，直到序列中的最后一条边。 32图论 Kukl . rsa算法的求解过程 ( )择权数最小的边，图 2中我们选取边 1选从BC;

合肥A芜湖B马鞍山c铜陵D安庆E池州F巢湖G滁州t宣城1 t六安J合肥A一一一一一一一一一一

芜湖 B 1 . 35 33一

一

一一

一

马鞍山Cl . 8一 35 . 4 21

一一

铜陵D 1 . 54 0.一 14 7. 109 95 3 3

一

一一

一一一

安庆E l - 7. 9. 9.一 53 l1l145 6 3 25 0 5 0