城市道路网表示的最佳方法选取刘一臻（福建师范大学地理科学学院福建福州350007）摘要：城市道路是社会经济活动和人们生活的基础设施，对于城市道路网的表示也是城市快速建模中的重要环节。

本文对城市道路网进行分解，归纳出路网中的几类基本的道路类型，根据拓扑学下的图论理论，对归纳出的不同道路类型进行拓扑表示，最后根据时间复杂度和空间复杂度进行不同方法表示的优化对比，得出邻接表可以较高效的进行城市道路网的表示。

关键词：图论、城市道路网、算法复杂度城市道路网络是社会经济活动和人民生活的基础设施，也是支持交通运输的底层网络。

许多实证研究发现城市道网是复杂系统，展现了无标度、分形结构、自组织等性质[1]。

城市道路体系随时间的推演不断发展变化，很多城镇最初发展并没有完善的城市规划，而是随着经济发展和人口增加逐步扩大，城市的地理空间结构因此呈现复杂多样的形态特征[2]。

1 城市道路分析1.2 城市道路网类型城市路网结构具备一定的规律性，可以把错综复杂的现象归结为基本单元的组合[3]。

道路系统只有在内部相互联系的各要素间形成合理的稳定的组合形态（如总体形态、等级配置、排列方式、衔接方式等），才能有效发挥道路系统的整体性能。

目前现有的道路网系统型式可归纳为四种主要类型：方格网式道路网、环形放射式道路网、自由式道路网、混合式道路网[4]。

1.2.1方格网式道路网方格网式道路网又称棋盘式，是最常见的一种道路网类型，它适应于地形平坦的城市。

用方格网道路划分的街坊形状整齐。

有的城市在方格网的基础上增加了若干条放射干线，以利于对角线方向的交通，但因此又将形成三角形街坊和复杂的多路交叉口。

方格网式道路网具有很好的规则性，相互道路相交垂直，可以将道路相交形式抽象成图1a中的形式。

在城区中，为了近距离出行的方便，在不同的街区间会出现交通小道，这些交通小道可以是沿对角线方向，也可以是沿道路中间穿过街区方向，可以抽象为图1b中的情况。

（a）（b）图1 方格网道路类型方格式道路网中复杂的道路网可以看作由简单的道路组合单元组成，（图2），方格式道路网中道路之间相互垂直，各个组成单元多由正方形道路网或长方形道路网组成，其中，为了不同街区间的方便，会在有的街区（即道路网中的方格组成单元）中穿插少许道路，而将方格单元切分成不同的单元。

图2 道路组成单元类型1.2.2环形放射式道路网环形放射式道路网系统起源于欧洲以广场组织城市的规划手法，多用于大城市。

放射形干道有利于市中心同外围市区和郊区的联系，环形干道又有利于市巾城区外的市区及郊区的相互联系。

环形放射形干道多起自市中心广场，道路多以锐角或者钝角相交。

在城市中，有的只有一个核心聚集区域，如一个城市中只有一个中心广场（图3a）；有的城市往往有几个核心聚集区域，即几个广场（图3b）。

若不考虑道路的转弯情况，即将环型道路中的环形干道看作直线道路，则环形放射式道路网可以看作是由方格道路网中相同的基本单元组成。

图3 环形道路网类型1.2.3自由式道路网自由式道路网常是由于地形起伏变化较大，道路结合自然地形呈不规则状布置而形成的（图4）。

这种类型的道路网没有一定的格式，变化很多。

能充分结台自然地形，但容易造成建筑用地分散，交通组织困难。

自由式道路网因地形影响较大，自身并没有严格的规律性，因而在用数据结构表示时有很大的困难。

图4 自由式道路示例（重庆市区）1.2.4混合式道路网在同一城市中，同时存在几种类型的道路网，组合而成为混合式的道路网。

还有一些城市，在现代城市规划思想的影响下，结合城市用地的条件和各种类型道路网的优点，形成了新型的混台式道路网。

常见的方格道路网加环形放射式的道路网是大城市发展后期形成的效果较好的一种道路网形式，如北京市（图5a）。

还有一种常见的链式道路网，是由一两条主要交通干道作为纽带链，好像脊骨一样联系着各类较小范围的道路网而形成的如兰州市（图5b）。

混合式道路网集合了方格式道路网和环形放射式道路网的几何特征，可以看作方格式道路网和环形放射式道路网的组合特征构成了混合式道路网的集合特征。

（a）（b）图5 混合式道路网2 基于图论的数据模型图论（Graph theory），是数学的一个分支，它以图为研究对象，研究顶点和边组成的图形的数学理论和方法。

道路网由节点(居民地及道路其它交点)的集合和路段(节点之间的道路段)的集合所构成，因此用图论方法研究道路网的空间结构信息具有特殊的优越性[5]。

2.3.1 邻接矩阵邻接矩阵是表示一个图的常用存储表示。

它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

在这里，用两个数组分别存储的元素为路网中的各个道路信息，形成基于路网的邻接矩阵。

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n 阶方阵：对于概括出来的城市道路网中的各个基本组成路网类型及相应的邻接矩阵如图6所示，路网基本组成单元相互组合，可以构成复杂的各类城市道路网类型，在此，不将道路的方向考虑进来，即路网是是无向图。

a bcde图6 路网基本类型的邻接矩阵2.3.2 网络矩阵上述邻接矩阵是表示一个道路网时，可以很好的表达出道路的结构，便与在计算中实现有向道路网的表达。

在城市道路中，不同的道路由于路况不同，车流量会出现差异，为解决这一问题，在路网线段中引入权重（图中括号内数值），表示不同路段的信息。

设G=(V ，E)是具有n 个顶点的图，则G 的网络矩阵是具有如下性质的n 阶方阵：其中W ij 表示i,j顶点之间路段的权重值，0表示一个计算机允许的、大于所有边上权值的数。

这样在遍历道路邻接网络时，可以同时得到道路转向和不同路段路况信息并在计算机中加以表示。

图7 道路网基本类型的网络矩阵2.3.3 邻接表邻接表是图的一种链式存储结构。

邻接表可以很好的表示有向图的数据结构，在表示无向图时，每个顶点对应一个单链表，第i个单链表的节点，包含顶点Vi 的所有邻接节点，又称连接表。

在无向图的邻接表中，每个表头节点对应一个节点，链接的是以该顶点为一端，指向线段的另一端节点。

城市道路网中的基本组成单元对应的邻接表表示法图8所示：图8 路网基本类型邻接表3 不同方法的对比分析道路图的数据结构实际上是研究如何把一个图存贮在电子计算机里。

对于某个问题究竟应该采用什么方式存贮，应考虑两个因素:第一，便于检索;第二，尽可能节省存贮单元。

计算机资源最重要的是时间和空间（即寄存器）资源，这里采用复杂度分为时间和空间复杂度。

3.1 时间复杂度在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

一个算法花费的时间与算法中语句的执行次数成正比例，算法中语句执行次数多，花费时间就多。

一个算法中的语句执行次数称为语句频度或时间频度。

由此计算不同城市道路网用三种数据结构表示时，时间复杂度如表1所示。

表1 不同算法的时间复杂度1 2 3 4 5邻接矩阵O(4) O(6) O(4) O(5) O(6)网络矩阵O(4) O(6) O(4) O(5) O(6)邻接表O(2) O(2) O(2) O(2) O(2) 3.2 空间复杂度空间复杂度S(n)是对一个算法在运行过程中临时占用存储空间大小的量度，即程序运行所以需要的额外消耗存储空间。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

得出城市道路网不同结构类型的不同表示方法的空间复杂度如下。

表2 不同算法的空间复杂度1 2 3 4 5邻接矩阵O(16) O(36) O(16) O(25) O(36) 网络矩阵O(16) O(36) O(16) O(25) O(36) 邻接表O(12) O(20) O(13) O(17) O(20) 3.3 不同方法的复杂度分析在不同的算法中，时间和空间复杂度越小，表示该算法越优。

用邻接矩阵来表示路网结构都比较简单和直接，但这种表示方法容易出现稀疏矩阵，就图的邻接矩阵表示需要用到n^2个整数位，其时间复杂度为0(n)，空间复杂度为O(n^2)，当用其表示交通路网，特别是大规模路网时则会浪费大量的存储空间。

网络矩阵在邻接矩阵的基础上增加了道路权重值，可以方便的表示出道路中的宽度、长度或者车流量等属性值，但是在计算机表示时，其时间复杂度与空间复杂度与邻接矩阵相同。

邻接表表示方法从时间复杂度来看，均优于邻接矩阵和网络矩阵，说明对同一算法运行次数较多，而在空间复杂度上也小于邻接矩阵和网络矩阵，即占用的计算机资源较少。

所以，从计算复杂度的角度考虑，邻接表对于城市路网的表示要优于了邻接矩阵和网络矩阵。

4 总结将城市道路抽象成基本组成单元，利用不同的算法进行表示，再基于算法复杂度进行算法最优的选取，能将城市道路关系在计算机中较好的表示出来。

通过对文中几种方法的算法复杂度分析得知，单从算法复杂度角度分析，邻接表对于城市路网的表示要优于了邻接矩阵和网络矩阵。

本文中的不足之处有以下几点：1、城市道路网中的方格道路网和环形放射式道路网可以用基本路网单元表示出来，但是随地形变化较大的自由式道路网没有办法很好的表示出来，自由式道路网的路网随机性较大，缺乏规律性，可以在后面的研究中结合地形、土地利用和政府区划图等相关资料进行归纳总结。

2、城市道路错综复杂，除了主干道具有严格的规律性外，不同的地方还会出现规划外的之路，这些道路在表示时也都没有表示出来，所以本文的表示也并不完善。

3、基于图论的城市道路网表示时，是将节点之间（即交叉口之间的道路）看成是直线道路，而实际当中两交叉口之间道路多是以弯道出现，因为本文在表示时并不能反映出这些弯道的情况。

参考文献[1]胡一父,吴勤旻,朱道立等.城市道路网络的拓扑性质和脆弱性分析[J].复杂系统与复杂性科,209,6(3):69-76.[2] Jiang B.topological pattern of urban street networks:universality and peculiarity[J].Physical ,207,384:647-655 .[3] 石飞,王炜.城市路网结构分析[J].城市规划,2007,31(8):68-73.[4]陈柏球. 我国大中城市道路网系统结构研究[D].中南大学,2009.[5]王家耀,崔铁军,王光霞. 图论在道路网自动选取中的应用[J]. 解放军测绘学院学报,1985,01:79-86.。