地理信息系统第五章

1、地理信息系统概论授课教师：贺晓慧联系方式： 主讲内容7 地图制图与输出1地理信息系统导论2地理信息系统的数据结构3空间数据获取与处理地理信息系统空间数据库45 空间分析的原理与方法6地理信息系统的应用模型分类 地理信息系统的设计与评价8空间和非空间分析的差别处理对象的差别：空间分析着重对象的位置信息，这些位置可以在地图上显示出来；非空间分析不考虑位置信息。分析方法的差别：空间分析是在考虑地理现象的空间依赖性的基础上，通常使用GIS和空间分析软件来完成；非空间分析不考虑空间要素的空间关联性，通常用数据库系统或统计软件包来进行。分析结果依赖性的差别：空间分析位置的改变导致分析结果的改变；非空间分析

2、，位置的改变不影响分析结果第五章 空间分析的原理与方法空间分析是GIS的重要组成部分，也是评价一个GIS功能强弱的主要标志之一，区别于其他信息系统的主要功能特征。定义：基于空间数据的分析技术，它以地学原理为依托通过分析算法，从空间数据中获取有关地理对象的空间位置、空间分布、空间形态、空间形成、空间演变等信息。基础：空间数据库方法：逻辑运算、数理统计分析、代数运算目的：不仅是自动制图，更是通过对空间数据的深加工，获取新的地理信息，提供空间决策信息。第五章 空间分析的原理与方法 GIS在发展过程中对空间分析有细致的研究，代表作有：1981年，Unwin的空间分析入门1990年，Haining的社会

3、与环境科学中的空间数据分析1994年，Goodchild的GIS环境下的空间分析等。第五章 空间分析的原理与方法分 类：按照空间数据的形式：矢量数据空间分析、栅格数据空间分析。按照Goodchild提出的空间分析框架，分为：产生式分析、查询式分析。空间分析的内容从宏观上，空间分析可以归纳为三个方面： 1.拓扑分析 2.属性分析 3.拓扑分析与属性联合分析主要的空间分析空间查询分析空间叠合分析空间邻近度分析网络分析数字地形模型分析(1)建立分析目的和评价标准：分析的目的是定义打算利用地理数据库解决什么问题，而标准则具体规定了将如何利用GIS回答用户所提出的问题。例：建一公园进行选址（目的）标准：

4、 交通便利、环境优雅 设计成环绕一个天然小河 可利用面积大、少沼泽地 (2)收集、输入空间和属性数据:包括地理底图数据、地籍数据、土壤数据等。数据准备在信息系统建立过程中是一个非常重要的阶段，需要投入大量的资金和人力来建立地理数据库。空间分析的步骤(3)做空间位置的处理和分析：为了得到所需数据，可能需要进行许多操作，如检索提取、缓冲、叠置等。作空间位置的处理和分析（包括检索、提取，缓冲区分析、叠置分析等）作属性数据的处理和分析（加所需的属性项、好地价）。 (4)准备表格分析的数据(包括地图和表格):大多数分析都要求利用空间操作得到一个（或一组）最终的数据层，还必须准备用于分析的数据，包括空间和

5、属性数据，所生成的层的属性表应包括利用逻辑表达式和算术表达式进行表格分析的信息，通常必须将进行分析时所需要的数据项加到属性表中。空间分析的步骤(5)进行表格分析：利用逻辑表达式和算术表达式，可以对进行空间操作时所获得的新的属性关系进行分析。 (6)结果的评价和解释：在通过表格分析获得了一个答案之后，必须对结果进行评价，以确定其有效性。(7)如有必要改进分析:如果感到很多进行的分析还有局限性和缺点，需要进一步改善，则可以返回适当的步骤重新分析。(8)以专题地图、文字报表形式作为正式结果，供决策用。空间分析的成果往往表现为图件或报表，图件对于凸显地理关系是最好不过的，而报表则用于概括数据并记录计算

6、结果。空间分析的步骤5.1 GIS空间查询空间数据库的一个主要功能就是能够进行空间数据的查询，即根据用户的要求，从数据库中找出符合用户要求的空间数据子集，提供给用户作进一步的处理工作。对空间实体的简单查找：属性查图形、图形查属性。属性查图形：按属性信息的要求查询定位空间位置。图像查属性：根据对象的空间位置查询有关属性信息。5.1 GIS空间查询相对复杂的空间数据查询功能：（1）针对空间关系的查询：查询一条公路途经的所有城镇；（2）针对非空间属性的查询：查询一个城市的人口数量；（3）结合空间关系和非空间属性的查询：查询距某条河流的距离大于500m（空间关系）、种植玉米（属性）、且面积大于800h

7、m2（既可以是空间计算，也可以是属性）的土地利用单元。5.1 GIS空间查询空间关系查询：（1）点-点查询：（2）线-点查询：（3）面-点查询：（4）点-线查询：（5）线-线查询：（6）面-线查询：（7）点-面查询：（8）线-面查询：（9）面-面查询：5.1 GIS空间查询另外一种表述对空间关系的查询主要是对空间实体间存在的拓扑、顺序、距离、方位等关系的查询。简单的点、线、面实体相互关系的查询包括：邻接查询：多边形邻接查询、线与线邻接查询等通过拓扑关系表查询。包含关系查询：可以多边形的定位查询，也可以使用空间运算执行（判断点是否落在面内）穿越查询：一般采用空间运算方法执行。根据一个线状目标的空

8、间坐标，计算出哪些面状地物或线状地物与它相交。落入查询：可以采用空间运算，即使用点在多边形内，线在多边形内或面在多边形内的判断方法。缓冲区查询：只是根据用户需要给定一个点缓冲、线缓冲或面缓冲的距离，从而形成一个缓冲区的多边形，再根据多边形检索的原理，检索出该缓冲区多边形内的空间地物。5.1 GIS空间查询空间关系查询：（1）点-点查询：（2）线-点查询：（3）面-点查询：（4）点-线查询：（5）线-线查询：（6）面-线查询：（7）点-面查询：（8）线-面查询：（9）面-面查询：5.1 GIS空间查询属性数据查询：主要是针对非空间的信息的查询大多数的GIS软件都将属性信息存储在关系数据库中，相对

9、成熟的关系数据库为GIS提供了完备的数据索引方法及查询手段。关系数据库管理系统基本都支持SQL（结构化查询语言）。5.1 GIS空间查询空间数据库查询语言：指从空间数据库中查找出所有满足空间约束条件和属性约束条件的地理实体的算法语言。常规的关系数据库查询语言是SQL，它可以作为属性数据的查询语言。SELECT 名称 FROM Province WHERE 面积50 AND 人口1000 面积单位（105km2） 人口单位（万人）SQL不能处理空间关系查询，要实现空间查询，需要对SQL进行空间扩展，但空间扩展的SQL还没有统一的标准。5.1 GIS空间查询空间属性联合查询：既包括查询空间位置关系

10、，又包括查询属性信息。分步骤借助于单独的空间关系查询和属性查询来实现。5.2 空间叠合分析一 空间叠合分析概念二 基于矢量数据的空间叠合分析 点与多边形的叠合 线与多边形的叠合 多边形与多边形的叠合三基于栅格数据的叠合分析 叠置分析(overlay analysis)（又称叠加分析），是指将同一地区、同一比例尺、同一坐标系统、不同信息表达的两组或多组专题要素的图层进行叠加，从而产生一个新图层的过程。 一、概念 其目的是为了有效地综合多种地理要素，从其中提取出隐含的数据信息。ABC基于矢量数据的叠置分析；基于栅格数据的叠置分析。二、分类矢量叠置分析的数学基础（空间逻辑运算）3、空间逻辑差运算；A

11、 - B =X XA 且 XB 1、空间逻辑并（或）运算；AB =X XA 或 X B 2、空间逻辑交（与）运算；AB = X XA 且 XB 4、空间包含；A B点与多边形的叠置线与多边形的叠置面与多边形的叠置基于矢量数据的叠置分析点与多边形的叠置：是计算多边形对点的包含关系，将一个含有点的图层叠加在另一个含有多边形的图层上，以确定每个点落在哪个多边形内，以便为图层上的点建立新的属性。AABB线与多边形的叠置：它也是计算一种包含关系，但与点不同的是，往往一条线跨越多个多边形，这时需要线与多边形边界求交，并将线目标进行切割、叠置，形成一个新的空间目标的结果集，同时产生一个相应的属性数据表记录原

12、线和多边形的属性信息。AABB基于矢量数据的叠置分析多边形与多边形的叠置：是最复杂的一种叠置，它需要将两层多边形的边界全部进行边界求交的运算和切割，然后根据切割的弧段重建拓扑关系，最后判断叠置的多边形分别落在原始多边形层的哪个多边形内，并建立起叠置多边形与原多边形的关系。其目的是通过区域多重属性的模拟，寻找和确定同时具有几种地理属性的分布区域。基于矢量数据的叠置分析基于矢量数据的叠置分析图层擦除（Erase）识别叠加（Identity）交集操作（Intersect）图层合并（Union）修正更新（Update）基于矢量数据的操作图层合并（Union）把两个图层的区域联合起来并保持来自输入地图和

13、叠加地图的所有地图要素。交集操作（Intersect）可以得到两个图层的交集部分，并且原图层的所有属性都将在输出图层上同时显示。识别叠加（Identity）识别图层的属性将赋给其所覆盖的输入图层的地图要素。图层擦除（Erase）擦除图层将擦除其所覆盖的输入图层内的要素。修正更新（Update）输入图层中被修正图层覆盖的那部分的属性将被修正图层的属性替代。基于栅格数据的叠置分析 栅格数据的叠置分析较矢量数据的叠置分析要简单得多，它主要是通过栅格间的各种运算来实现。可以对单层数据进行各种数学运算如加、减、乘、除、指数、对数等等，也可以通过数学关系式建立多个数据层之间的关系模型。这种基于数学运算的数

14、据层间的叠加运算，在地理信息系统中称为地图代数（代数运算和逻辑运算）。 基于栅格数据的叠置分析 栅格数据的叠置分析条件：具备两个或多个相同地区的相同行列数的栅格数据，栅格单元的大小也相同。 栅格叠合分析的结果是一个新生成的栅格数据，其中的每一个栅格的数值都是由参与计算的原栅格数据计算得到的，栅格叠合通过计算产生新的空间信息。设a、b、c等表示不同专题要素图层上同一个栅格单元的属性值，f表示各层上属性与用户需求之间的关系，A表示叠加后输出层的属性值，则可有这样的关系式： A=f（a,b,c）基于栅格数据的叠置分析基于栅格数据的操作基于栅格的地图代数运算或逻辑运算。2446334633772254

15、23643366-=0-21-2-102-200-1-1结果特征：运算后得到的新属性值可能与原图层的属性意义完全不同。基于栅格数据的叠置分析点与多边形的叠置： 如何得到某省区内雨量站点的个数？ 如何知道某个水文站点属于哪个行政区划？ 如何获取某城市的邮局分布密度？ 如何了解某个水质监测井属于哪个等级的水资源分区？ 应用*1 *3 *4 *2A DB C点 属性1234多边形 属性1 属性2ABCD点 多边形 点属性 面属性1 面属性21 A2 D3 C4 B点与多边形的叠置：例如将水井与规划区图层相叠置，可确定每口井所属的规划区范围。实例线与多边形的叠置： 如何得到某省区内高速公路的长度？ 如

16、何知道某段公路属于哪个行政区划？ 如何求取某城市的河网密度？ 如何了解某条河流流经哪几个行政区？ 如何确定哪种地层岩性中发育了断层？ 应用例如：当确定某一行政区内各种等级道路的里程数时，就需要将道路图与境界图相叠置，计算弧段与多边形边界的交点，在交点处截断弧段，并对弧段重新编号，建立弧段与多边形的归属关系。线与多边形叠置分析实例多边形与多边形的叠置： 如何得到某省区内有哪几种土地利用类型？ 如何知道不同级别的灾害分区中的植被覆盖情况？ 如何获取某行政区划内的地层岩性分布情况？ 应用日喀则地区沙漠化类型分布图日喀则地区行政区界线图有日喀则地区的行政界线图层和通过遥感技术提取的该区沙漠化类型分布图

17、层，求日喀则地区各县沙漠化类型统计数据。图层1图层2实例行政区界图属性表图层1：图形，属性表日喀则地区行政区界线图日喀则地区沙漠化类型分布图属性表图层2：图形，属性表日喀则地区沙漠化类型分布图空间叠置图叠置图属性表使用IDENTITY命令，进行两图层空间叠置，得到叠置图叠置图层属性表图层1属性表图层2属性表栅格数据的叠置分析： 遥感数字图像的拼接； 环境评价及分区； 灾害危险度分区； 土地利用与土地覆被变化（LUCC）； 应用101060601010206030303060101060601010306030303060-=0000001000000土地利用变化区域探测80年遥感影像90年遥感

18、影像点变换后影像通过80和90年两期影像的相减运算后得到变换影像，如果：变换影像值 0；说明该区未发生变化变换影像值 0；说明该区已发生变化10 耕地20 居民点30 水域40 草地50 未利用地60 林地Legend注意：此处的遥感影像可以是分类结果，也可以是原始的遥感影像。在一般应用中，多使用原始的遥感影像，可提高变化探测速度。实例1实例2叠置分析的目标是分析在空间位置上有一定关联度空间对象的空间特征和专题属性之间的相互关系，其结果不仅可以产生新的空间关系，还可以生成新的属性特征关系，能够发现多层数据间的相互联系和变化等特征，使我们可以提取并挖掘出大量的隐含信息。小结而叠置分析的强大功能可

19、以在我们众多的GIS（ArcGIS、SuperMap、ERDAS等）软件中均可以轻松实现。小结5.3 空间邻近度分析空间邻近度描述了地理空间中两个地物距离相近的程度，邻近度分析是空间分析的一种重要手段。所研究道路沿线的废气污染或河流沿线的供水能力公共设施的服务区域划分确定工程建设引起的搬迁范围等空间缓冲区分析Voronoi多边形分析5.3.1 缓冲区分析的定义缓冲区（影响区、影响带）：是指地理空间实体的一种影响范围或服务范围。缓冲区分析：是围绕空间的点、线、面实体，自动建立其周围一定宽度范围内的多边形，用以识别这些实体或主体对邻近对象的辐射范围，以便为某项分析或决策提供依据。基本思想就是给定一

20、个空间实体或集合，确定它们的邻域，邻域的大小由领域半径R来确定。 在进行空间缓冲区分析时，通常要将研究的问题抽象为以下三类因素来进行分析：（1）主体：表示分析的主要目标，一般分为点源、线源和面源三种类型。（2）邻近对象：表示受主体影响的客体，例如行政界限变更时所涉及的居民、森林遭砍伐时所影响的水土流失范围等等。（3）作用条件：表示主体对邻近对象施加作用的影响条件或强度。5.3.2 缓冲区分析的组成要素根据主体对邻近对象作用性质的不同，一般可采用以下三种不同的分析模型：线性模型：用于当主体对邻近对象的影响度（F）随距离(r)的增大而呈线形形式衰减时。幂函数模型：用于当主体对邻近对象的影响度随距离

21、的增大而呈现二次形式衰减时。指数模型：用于当主体对邻近对象的影响度随距离的增大而呈指数形式衰减时。 三种分析模型基于矢量数据的缓冲区分析；基于栅格数据的缓冲区分析。5.3.3 缓冲区分析的类型基于点特征基于线特征基于面特征点缓冲区 以点为圆心，以一定距离为半径画圆所围成的区域。 用途：针对点要素的一定半径范围的分析。 相互靠近的圆可以相互重叠单级缓冲区多级缓冲区 线缓冲区 分别对每一个顶点和每条边（按缓冲距离在线的两侧作平行线，在线的端点处作半圆与平行线连接成封闭的区域）生成缓冲区，然后对这些缓冲区多边形进行叠置操作。 用途：针对线要素的一定范围带状范围的分析。 双侧对称缓冲区BdR面缓冲区

22、首先生成多边形周长的缓冲区（线缓冲区），多边形缓冲区有内外之分。外缓冲区在面状地物的外围形成缓冲区、内缓冲区则在面状地物的内侧形成缓冲区。 缓冲区综合多重缓冲区生成 以不同的半径首先分别生成一定宽度的缓冲区，然后对不同半径的缓冲区进行叠置操作。 多重缓冲区有利于空间分析中针对不同的距离采用不同的处理方法。同样也可以对不同的空间实体根据需要，分别采用不同距离生成缓冲区，通常将缓冲区的距离存储在空间实体的属性表的一个字段里。 5.3.4 矢量缓冲区的建立 从原理上讲，缓冲区的建立相当简单，建立缓冲区仅是以点状地物为圆心，以缓冲区距离为半径绘圆即可，线状地物和面状地物的缓冲区的建立也是以线状地物或面

23、状地物的边线为参考线，作它们的平行线，再考虑端点圆弧，即可建立缓冲区。 对于简单情形，缓冲区是一个简单多边形，但当计算形状比较复杂的对象或多个对象集合的缓冲区时，就复杂得多。可变距离缓冲区示意图当对特征规定不同缓冲区宽度时的处理空间缓冲区建立应注意的方面:根据不同属性建立不同的缓冲区宽度 空间缓冲区建立应注意的方面:当缓冲区发生重叠时的处理多个特征缓冲区图形的处理拓扑识别，删除缓冲区内弧段5.3.5 栅格缓冲区的建立 基于栅格结构也可以作缓冲区分析，栅格缓冲区的生成可以通过两个步骤来实现。首先，对需要做缓冲区的栅格单元作距离扩散，即计算其他栅格到要做缓冲区的栅格距离。然后按照设定的缓冲区距离提

24、取出符合要求的栅格单元。缓冲区应用意义 核电站的5公里缓冲区 紧急疏散区 我国30公里内缓冲区 沿边地区 海岛国家的n公里外缓冲区 领海 高速公路的50米缓冲区 噪音的严重污染区 空间缓冲区分析实例5.3.6 Voronoi多边形分析 其原理是根据离散分布的已知数据点对研究区域进行划分，使得划分成的多边形覆盖整个研究区域，形成一个Voronoi图，且每一个多边形中仅包含一个已知的数据点。则可以用该已知数据点的数据来表达和分析该多边形内的所有其他数据点，所以常用于空间插值计算。荷兰气候学家AHThiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角

25、形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。 其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心 泰森多边形的性质是：1、每个泰森多边形内仅含有一个离散点数据；2、泰森多边形内的点到相应离散点的距离最近；3、位于泰森多边形边上的点到其两边的离散点的距离相等。4、所有的泰森多边形都是凸多边形5、顶点是外接圆的圆心6、所有的外接圆内部不包含已知点如何实现在每棵树的周围圈上围栏？ 如何拓宽一条道路？ 如何确定在距学校的一定范

26、围内禁鸣喇叭？ 如何定出河流或湖泊周围保护区的范围？ 如何选择汽车服务区的定位？ 应用实例1已知一伐木公司，获准在某林区采伐，为防止水土流失，规定不得在河流周围 1km 内采伐林木。另外，为便于运输，决定将采伐区定在道路周围 5km 之内。请找出符合上述条件的采伐区，输出森林采伐图。解题思路 ： 首先要以区域的道路分布图、河流分布图、森林分布图为数据源。解题流程图： 道路分布图森林分布图河流分布图结束生成道路周围5km缓冲区叠置生成河流周围1km缓冲区叠置将该地区具有相同比例尺且进行配准的道路分布图、河流分布图、森林分布图，进行预处理和数字化；利用河流分布图生成1km的等距缓冲区；利用道路分布

27、图生成5km的等距缓冲区；森林分布图中可采伐林地、道路缓冲区及河流缓冲区图进行叠置，叠置条件表达式为: 采伐区 森林分布图中可伐林地 道路周围5km缓冲区 非河流周围1 km缓冲区将上述3张图进行两两叠置，所得结果即为森林采伐图。 解题详细步骤： 已知一湖泊，要求在它周围5000m 内必须禁止任何污染性工业企业存在，在它周围500m 内必须禁止建筑任何永久性建筑物。实例2解题思路 ： （1）先建立缓冲区；（2）同现有污染性工业企业图叠置，显示在范围内应禁止的污染性工业企业；（3）同现有永久性建筑物图叠置，显示在范围内应禁止的永久性建筑物。5.4 空间网络分析网络分析的概念网络分析的基础网络分析

28、的功能网络分析的常用方法网络分析的应用网络是一个由点、线的二元关系构成的系统，通常用来描述某种资源或物质在空间上的运动。网络分析(network analysis) 是通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络结构及其资源等的优化问题进行研究的一种空间分析方法。这里的网络是指由地理实体抽象而形成的图或者网络图等表现形式，如交通道路网、供水网、管道网和水系网等。 概念 网络分析的理论基础是运筹学和图论。在地理信息系统中，网络分析功能依据图论和运筹学原理，在计算机软硬件支持下，将与网络有关的实际问题抽象化、模型化、可操作化，根据网络元素的拓扑关系，通过考察网络元素的空间、

29、属性数据，对网络的性能特征进行多方面的分析计算，从而为制定系统的优化途径和方案提供科学决策的依据，最终达到使系统运行最优的目的。运筹学是近代形成的一门应用科学，主要研究各种有组织系统的管理问题及其经营活动，一般使用定量化的研究方法，尤其是运用数学模型来解决问题。图论是运筹学中有着广泛应用的一个分支，主要研究事物及其关系，任何一个能用二元关系描述的系统，都可以用图形提供数学模型。基础图的几个基本概念： 图是由点集合V和V中点与点之间的连线的集合E构成的二元组（V,E）；其中V叫图中的顶点或结点，E叫图的边； 一般用G=(V,E)来表示一个图，通常，也将图G的顶点集和边集分别记为V(G)和E(G)

30、 ； 两个端点重合的边称为环； 若两条边的端点是相同的，则称其为重边； 既没有环也没有重边的图称为简单图。基础 如果图中的边是有向的，则称为有向图，其中的边叫做弧或链； 在无向图中，首尾相接的一串边的集合叫做路；有向图中，顺向的首尾相接的一串边的集合叫做有向路； 如果一个图中，任意两个节点之间都存在一条路，则称之为连通图，具有连通性； 若给图中的每一条边赋以一个实数，则该数称为边的权数，不同情况下权数的含义不同。基础将图论中的网络概念引入到地理空间中描述和表达基于网络的地理目标，就产生了地理网络。地理网络是GIS中一类独特的数据实体，是由若干线实体相互连接形成的系统，它除了具有一般网络的边、节

31、点间的抽象拓扑意义之外，还具有空间定位上的地理意义和目标复合上的层次意义。基础网络数据模型： 网络数据模型是现实世界网络系统的抽象表示。按照几何形态，空间实体被抽象为点、线、面目标，构成网络的最基本元素是线性实体以及这些实体的连接交汇点。用公式NET=(V,E)来表示。 基础网络数据的基本组成：链（弧）（link）： 链是构成网络的骨架，是现实世界中各种线路的抽象，也是资源传输或通信网络的通道，可以代表公路、铁路、街道、航线、水管、输电线、河流等。 链包括图形信息和属性信息，其属性信息包括阻碍强度和资源需求量。链的阻碍强度是指在通过一条链时所需花费的时间或费用等，如资源流动的时间、速度等。链的

32、资源需求量是指沿着网络链可以收集到的或者可以分配给一个中心的资源总量。基础网络数据的基本组成： 结点（node）：链的端点，又是链的汇合点。 障碍（barrier）：禁止资源在链上流动的点。 拐点（turn）：出现在网络链中的分割结点上。 中心（center）：网络中具有一定的容量、能够 接受或分配资源的结点。 站点（stop）：在路径选择中资源增减的结点， 如库房、车站等。基础功能路径分析连通分析拓扑排序资源分配流分析动态分段地址匹配方法最佳路径分析连通性分析拓扑排序资源分配路径分析是GIS中最基本的功能，其核心是对最佳路径的求解；从网络模型的角度看，最佳路径的求解是在指定网络的两个结点之间

33、找一条阻碍强度最小的路径；阻碍强度可以是所经路径需要花费的时间，也可以是所经路径的长度。方法最佳路径分析求最佳路径的最好方法是Dijkstra的贪婪算法。即采用逐步构造最优解的方法，在每个阶段都做出一个在当前情况下最优的决策，直到获得最后结果。如下图城市通信网络：方法最佳路径分析求最佳路径的步骤：先找出起始结点并在路径中加入；从剩余的结点中找距起始结点最近的顶点并加入路径；重复步骤，直至目的结点。方法最佳路径分析方法连通性分析连通分析主要包括两方面的问题：连通分量求解问题分析从某一结点出发能够到达的全部结点或边；最少耗费连通求解问题即在耗费最小的情况下使全部结点相互连通。方法连通性分析连通分析

34、的求解网络的遍历算法：深度优先搜索（DFS）：假定图中某个顶点v1为出发点，首先访问出发点v1，然后任选一个v1的未访问过的邻接点v2，以v2为新的出发点继续前面的步骤，直至图中所有顶点被访问过。图的深度优先搜索是一个递归过程，类似于树的前序遍历，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。方法连通性分析广度优先搜索（BFS）：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其它顶点，直至所有顶点都被访问到。它类似于树的按层次遍历，其特点是尽可能优先对横向搜索，故称之为广度优先搜索。方法连通性分析如下连通图的两种搜索

35、方法：方法连通性分析深度优先搜索广度优先搜索在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往存在两种关系：先后关系，即必须在一项目完成之后，才能开始实施另一个子项目；子项目间无关系，即两个子项目可以同时进行，互不影响。项目的实施可以构成一个有向图，现在要从这个有向图上找出一个施工流程图，以便顺利进行施工，解决这个问题可以采用拓扑排序的方法。方法拓扑排序设G=（V，E）是一个具有n个顶点的有向图，V中顶点的序列V1，V2，Vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若在有向图G中，从顶点Vi到Vj有一条路径，则在序列中顶点Vi必须排在顶点Vj之前。找一个有向图的一个拓

36、扑序列的过程称为拓扑排序。 方法拓扑排序有向图拓扑排序算法的基本步骤：从图中选择一个入度为0的顶点，输出该顶点；从图中删除该顶点及其相关联的弧；重复执行、直到所有顶点均被输出。可以证明，任何一个无环有向图，其全部顶点都可以排成一个拓扑序列。而且其拓扑序列不一定是唯一的。方法拓扑排序以右图为例： 某施工工序的有 向图，对其进行 拓扑排序。方法拓扑排序结果：对这个有向图进行拓扑排序可得到一个拓扑序列：C1，C2，C7，C6，C3，C4，C5。也可得到另一个拓扑序列C1，C7，C2，C3，C6，C4，C5。资源分配就是为网络中的网线和结点寻找最近(这里的远近是按阻碍强度的大小来确定的)的中心(资源发散或汇集地)。资源分配是模拟资源如何在中心(学校、消防站、水库等)和它周围的网线(街道、水路等)、结点(交叉路口、汽车中转站等)间流动的。根据