城市交通路网数据模型的构建及其拓扑结构的研究

1、城市交通路网数据模型的构建及其拓扑结构的研究李菲肖洪祥（桂林工学院电子与计算机系，桂林541004）摘要基于图论的思想，根据节点、路段和转向这三个主要的网络要素构建了一个城市交通路网模型，并将其抽象成带转 向的赋权有向图。同时.通过一个含4节点、8路段的示例路网着重研究了交通路网拓扑结构的五种表达方式。研究表明，路 网拓扑结构的表达方式不能单靠各方法的时间空间复杂度来决定，还需权衡问题求解算法的特点。关键词路网赋权有向图拓扑结构中图法分类号tp311. 12;文献标志码 a交通的发展是国家兴旺发达的重要标志之一。 近年来，交通的拥挤、道路的阻塞越来越严重地困 扰着世界各国城市。因此，深入研究城

2、市交通路网的数据模型及其拓扑 结构是非常必要的，交通系统的规划大多建立在它 的基础上。1交通路网的基本元素城市的交通路网主要由大量相邻或相交的道 路组成，经研究发现，一条道路通常在与若干条這 路相连的同时又与若干条道路相交。但若单纯的 只以道路为对象来研究交通路网拓扑关系的话，其 数据结构会显得很复杂。因此，本文以交通路网中 的交叉口为基点展开讨论，定义交叉口为节点，s 相邻节点之间的道路为路段。这样，整个路网可定 义成一个由大量的节点和路段组成的复杂网络 系统。但交通路网不同于简单的道路网，道路网只是2009年1月9日收到广西教育厅科研项目（桂教科研200701lx336）资助第一作者简介:

3、李菲（1983），女，桂林工学院电子与计算机系， 硕士.研究方向：人工智能，模式识别。r3nail: litci07392001 sina como节点与路段的集合，交通路网中的道路还包含了车 流的行驶方向和各种行驶限制策略等，如：单向行 驶、禁止左转弯等。因此，路网又进一步定义成包 含'节点、路段、转向"三个基本要素的交通路网11。2交通路网的数据模型2 1图论思想121图论（graph theory）是数学的一个分支，它以 图为研究对象。图论中的图是由若干给定的点s 连接两点的线所构成的图形，这种图形通常用来掊 述某些事物之间的某种特定关系，用点代表事物 用连接两点的线表

4、示相应两个事物间具有这利 关系。2 2模型构建根据图论的思想，将路网抽象成一个带转向的 赋权有向图,路网模型如下/3/:t= （n, r,w, f）o其中：r表示一个城市的交通路网模型，n = z2fi / = 1, 2, n/表示交通路网中节点的集合，r = r<n hj/表示交通路网中路段的集合， %为路网中任意相邻的两个节点， >指 从川节点进入到节点离开的路段，r<nh >与>表示的行驶方向完全相反,w = / w < nit nj > /表示交通路网中路段权值的 集合；f = !f( < nh nj > , < n, nk

5、> ) / 表示路段的转 向，若/= + ，则说明禁止从路段r<nhnj转向 路段，<巧，叫。3路网的拓扑结构及其表示方法a 1拓扑学拓扑学也是数学的一个分支，它属于几何学的 范畴，但它又与通常的平面几何、立体几何很不相 同。通常的平面几何或立体几何研究的对象是点、 线、面之间的位置关系以及它们的度量性质。拓扑 学对于研究对象的长短、大小、面积、体积等度量性 质和数量关系都无关，它旨在研究各对象之间的结 构关系。a 2路网拓扑结构的多种表示方法交通路网的拓扑关系主要在于"节点路段31向"之间的拓扑关系，当交通路网被抽象成有向医 时，其拓扑结构问题就转化成了

6、有向图的结构问题。有向图在数学和计算机领域已经被研究的比 较透彻，关于它的表示方法现已出现了很多种，如： 关联矩阵、邻接矩阵、邻接表等/4 5/。现以实际交通网中一个简单的带转向的路网 ® 1)来具体研究一下这几种典型的方法。表路段的行驶方向，虚线箭头代表路段之间的转 向，小括号内的数字代表路段权值。3. 2 1邻接矩阵邻接矩阵是表示图形中顶点之间相邻关系的矩阵。若设图g=(v, £)是一个有个节洁的图，其中v表示节点，£表示边，则图的邻接矩阼&是一个二维的矩阵。对于该矩阵，若顶点至后在一条边，则认为第项的值为1,否则第(4 y)项的值为0。即； 1, i

7、f< 4 j> or (i, j)ac (i，j) 1.k 0, othenvise上述示例路网用邻接矩阵表示如图2。12341co88oo26oo57310cooo154oo7ooooal a2 bi b2 cl c2 d eal01000010a210001000bi00010000b200100101cl00100101c210001000d00010000e01000010(b)图2示例路网节点(a)、路段转向的邻接矩阵表示3. 2 2邻接表邻接表是邻接矩阵的改进，它对图中的每个t 点都建立一个邻接关系的单链表，并把它们的表头 指针存储。有向图的邻接表就是所有节点的邻接个单

8、元实际对应于一条路段，路段的起点取决于链 表头.终点取决于该单元存储的节点。设g(v, £)是一个有0)个节点的图，右 邻接表的表示法中每一个节点对应一个链表，箭头 代表指向该链表下一个单元的指针，代表链表纬 束。现用邻接表来表示上述示例路网，如图3所示。图3示例路网的邻接表表示3. 2 3双向邻接表(十字链表)双向邻接表是对邻接表和反向邻接表的合二为一，又叫十字链表。在这种结构中每个节点有2 个单向链表，一个列出该节点的所有的邻接节点， 另一个列出该节点的所有反向邻接节点。示例路 网的双向邻接表如图4所示：图中由每个节点引出 的横向链表串起了所有的邻接节点，竖向链表串起 了所有的反

9、向邻接节点。3.2.4星形表星形表实际上是邻接表的一种以 顺序表为结构的具体形式，它用两个数组代替了邻接表中的多 个单向链表。其中一个数组依次存储各个节点的 所有邻接节点，另一个数组则记录每个节点的邻接 节点在前一个数组中的起始地址。星形表也分为 前向星形表、反向星形表和双向星形表。 a 3几种表示方法的比较经研究发现，用邻接矩阵来表示路网拓扑结构都 比较简单和直接，但这种表示方法容易出现稀疏矩 阵，如图的邻接矩阵表示需要用到 x。个整数位，其 时间复杂度为0 gd,空间复杂度为0 (n2;,当用其表 示交通路网.特别是大规模路网时则会浪费大量的存 储空间。下面以图1路网为例,就各表示法的时间

10、和 空间复杂度说明其缺点和优越性f见表u。表1各表示法的时间空间复杂度比较表示法查找邻接节点查找反向 邻接节点时间复杂度插入或删 除某条弧空间复杂度邻接矩阵o (4,o(4.o( ,邻接表反向(“2,<"8.o(i2.邻接表十字o<o( 2 .0( ,o(2f链表星形表 反向星形表o( ,o(2f双向星形表o(2.o(2fo(2)o(s)oi2)o(2)o(2)0(3)o(2由表1发现，就空间复杂度来说，邻接矩阵的存储效率明显不如邻接表和星形表，但就时间复杂度中的插入弧来说，邻接矩阵的效率又明显优于星开;表。因此在实际运用中，到底该以哪种表示法来表示问题模型，我们需将问题

11、求解算法的特点和各？示法时间空间复杂度结合起来考虑。总的来说，叶字链表的效率是最好的，它既可以快速检索邻接节点，也可以快速检索反向邻接节点。a1 a2 bi b2 ci c2 d e图4示例路网路段转向的双向邻接表表示4结论数据模型是对真实世界中系统的抽象描述，本 文中构建的城市交通路网数据模型尽可能的完成 了对实际交通路网的抽象，并将其用多种表示方过 表示出来。通过分析各表示法的时间和空间复杂 度,我们发现具体问题该具体分析，表示法的选抟 取决于求解问题的特点和表示法的效率。参考文献1任刚.交通管理措施下的交通分配模型与算法.南京：东南大学出版社，2007_2（美）buckley f, le

12、winterm.图论简明教程.李慧霸.王凤芹.译.北京:清华大学出版社，2005、樊月珍.基于交通流的车辆动态路径诱导方法研究.博士学位 3论文.北京：中国农业大学，2005殷人昆，陶永雷.谢若阳.等.数据结构.北京：清华大学出版 4 社，1999（美）sahnis数据结构、算法与应用一c+ +语言描述.汪诗 5林、孙晓东，译.北京:机械工业出版社，2000urban transportation road network data m odel and its topology studylifei，xpvo hong2xiang(dcpartncnt of fjcctronic and c

13、omputer, guilin university of technobgy, guilin 541004, p. r. china)abstract based on the thought of the graph theory, and according io the nodes，the roads and the directions to build an urban transportation toad network model，and ab strac t a s a o rien ted graph with weight are presented at the same tine, focusing on the five egression of the transport neworik topobgy through the toad netvoik with 42iodc and 8 2ioad section is p re sen ted ton research shows that the