衡阳市石鼓区由于建设完成时间较长，在设计之初未实行雨污分流制度，导致雨污水管线串接、混接，管网中的流动物质相互流通，其结果是污水流入雨水管道中，污水通过径流、排放入河等方式直接进入自然水体，不仅污染水质，而且给市区防洪带来极大的压力；雨水流入污水管道中，污水末端处理量增大，导致不必要的人力物力资源浪费。要解决雨污合流带来的问题，要精确获取管网之间的连通关系，查找雨水排放口中污水来源，从源头上切断污水直接入河，获取城市雨污水排放口中雨污水来源、流动量，为污水治理提供精确的数据支持。当前大部分的管线系统都将管线数据预先处理成网络数据集，通过ArcGIS提供的网络分析功能实现管网连通性分析^[1-5]，这种方法需要对数据进行大量预处理(数据建模)，而且要预先设置各种条件，对管网数据的要求高，且容易发生错误，容错性不高，导致分析失败或分析结果不完整。

本文依据《衡阳市地下管线数据采集建库标准》对排水管网数据特征进行分析，依据广度优先搜索的基本思想，基于管点的物探点号唯一和定向的准则，以两条连接管线必定存在一个相同的起点物探点号或者终点物探点号为判断依据，获取管线上下游连接管线，实现管线连通性分析，获取城市雨污水排放口中雨污水来源、排污/水量，为排水系统末端污染治理提供辅助决策支持。

1 排水管网数据特征分析

1) 定向，即具有确定的流动方向。排水管网中物质流动的方向是确定的，并以属性的方式存储在数据中。在雨污水管网中，流向值为0时，表示雨污水流动方向与管网数字化方向一致(即从线段起点流向终点)；流向值为1时，表示雨污水流动方向与管网数据化方向相反(从线段终点流向起点)。

2) 管点的物探点号唯一。在排水管网中，管点的物探点号属性值不为空且唯一，管点能以物探点号进行唯一标识。管线与连接管点的关系通过起始或终止管点物探点号实现，即管线的起始管点物探点号标识了管线数字化方向起点所连接的管点。

通过对排水管网数据的特征分析可以得出，以流向属性为特征属性，基于物探点号，可以直接通过属性获取管网之间的连通关系。

获取上游管网。通过流向属性，获取管线流入口对应的管点物探点号, 通过物探点号查询对应的管线。即如果流向属性值等于0，则流入口对应的物探点号为管线的起始物探点号；反之为管线的终点物探点号。

获取下游管网。通过流向属性，获取管线流出口对应的管点物探点号，通过物探点号查询对应的管线。即如果流向属性值等于0，则流出口对应的物探点号为管线的终点物探点号；反之为管线的起始物探点号。

在获取了每条管线的入水口与出水口之后，通过物探点号进行搜索，可以得到管线的上游或者下游管线，实现管网连通性分析。

2 基于广度优先的管网连通性分析算法 2.1 广度优先搜索算法

广度优先遍历(breadth first search, BFS)是连通图的一种遍历策略^[6]。广度优先搜索算法中“层次”概念很重要，只有当同一层的所有节点都搜索完，才能进行下一个层次节点的搜索，即广度优先。广度优先搜索遍历类似于树的按层次遍历。

对于无向连通图，广度优先搜索是从图的某个顶点V₀出发，在访问V₀之后，依次搜索访问V₀的各个未被访问过的邻接点W₁、W₂、…，然后按顺序搜索访问W₁的各未被访问过的邻接点，W₂的各未被访问过的邻接点，…。从V₀开始，由近至远，按层次依次访问与V₀有路径相通且路径长度分别为1、2、…的顶点，直到连通图中所有顶点都被访问一次。

从连通图的顶点V₀开始，进行基于广度优先搜索的步骤如下：①从顶点V₀开始进行搜索，将其访问标志设为已被访问，即visited[i]=1；②依次访问顶点V₀的各个未被访问过的邻接点，将V₀的全部邻接点都访问到；③分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问过的顶点的邻接点都被访问到。依此类推，直到图中所有顶点都被访问完为止。

节点的访问顺序为：V₀→V₁/V₂→V₃/V₄/V₅/V₆→V₇/V₈，如图 1所示。

2.2 连通性分析

本文基于管点的物探点号唯一准则，以两条连接管线必定存在一个相同的起点物探点号或者终点物探点号为判断依据，实现管线连通性判断。搜索终止条件为：①无连接管线；②当前管线与连接管线流出口/流入口对应的物探点号一致；③环路情况。连通性分析流程如图 2所示。

判断管线V₀和V₁的连通性并获取连通路径，具体判断步骤如下：①以V₀为初始管线，以起点物探点号S₀作为初始搜索条件；②通过S₀搜索起点物探点号或终点物探点号为S₀的所有管线集合List，并判断集合中每条管线流向是否与V₀一致，如果一致，则加入待搜索集合Queue，否则不加入；③依次以Queue中的每条管线中不等于S₀的起始物探点号或终点物探点号S₁作为搜索条件，重复步骤②，直到搜索到V₁；④如果List或Queue为空(表示无连接管线)，或搜索到V₀(表示有环路的情况)，或搜索到管线的流出口为S₀(表示产生对流情况)，表示该方向上V₀与V₁不连通，搜索终止；⑤以V₀终点物探点号S₁作为初始搜索条件，重复步骤②~④，直到查找到V₁；⑥如果从V₀管线两个方向上都没搜索到V₁，则表示V₀和V₁不连通。

以上是实现连通性分析的步骤，查找上游管线，则以V₀的流入口对应的物探点号为开始搜索条件, 按照步骤②~④进行搜索, 直到没有连接管线为止; 查找下游管线，则以V₀的流出口对应的物探点号为开始搜索条件, 按照步骤②~④进行搜索, 直到没有连接管线为止。

3 算法的实现与应用

将本文设计的基于广度优先的连通性分析算法应用于衡阳市石鼓区地下综合管线GIS系统，系统采用B/S架构，以ArcGIS API for Silverlight为主要技术手段，在实现了地下综合管线的定位、查询、统计、空间分析等基本GIS信息系统的功能的基础上，针对排水管线实现了雨污合流管点和管线分析、管网上下游分析、多点同源管网分析、排放口分析和排水量分析等专门针对合流管网分析的功能。雨污合流管网相关分析功能在精确定位合流管点与管线的基础上，准确获取与之相连通的所有管网信息，分析上游来源和下游排放口，为排水系统末端污水处理、科学化的城区污水排放规划和管理提供辅助决策支持。具体分析界面如图 3所示。

4 结束语

本文从排水管线数据特征出发，以管点物探点号唯一为关键，以流向为特征属性，基于广度优先搜索算法，设计并实现基于广度优先的排水管网连通性分析算法，并应用于衡阳市石鼓区地下综合管线GIS系统中。利用该系统准确获取合流雨污水管点/线上下游管网分布情况，查找污水管网与雨水管网混接处，检查各雨水排放口的上游管线，精确获取末端污染来源，为末端污染治理提供直观科学的数据支持，使城市基于设施建设与GIS应用技术得到有机的结合，从而使城区污水排放得到现代化的规划和管理。