第29卷第3期 2017年6月
浙江水利水电学院学报
J. Zhejiang Univ of Wat. Res & Electric Pow.
Vol.29No.3 Jun.2017
基于余枝搜索的最小独立闭合环自动搜索算法
谢海燕，王超
（上海岩土工程勘察设计研究院有限公司，上海200438）
摘要：在控制测量、水准测量数据处理中，为实现快速有效的进行最小独立闭合环的自动搜索，基于生成树和余树，利用数组的存储结构，由余枝两端向外索，遇同名点后获得闭合环，再通过闭合环的独立性判断，实现最小独立闭合环的快速有效搜索.进而利用该程序对2011年上海市闸北区水利普查项目中的部分水准测量结采进行进
行验证，证明所搜案的闭合环在常规网型中可以有效的做到最小和独立，关键调：最小独立闭合环；生成树；自动搜索；算法
中图分类号：P211
文献标志码：A
文章编号：1008-536X(2017)03-0068-04
AMethod of Auto-searching Least Closed Loops Based on Spare Branch
XIE Hai-yan, WANG Chao
( Shanghai Investigation and Design Institute Co. , Ltd. of Geotechnical Engineering, Shanghai 200438, China)
Abstract : In the data processing of control surveying and leveling, in order to quickly and effectively carry out auto-search least closed loop, based on spanning tree and spare branch, a 2-D array storage structure is used to search at both ends of spare branch and to get closed loop when meeting the same point. The independent judge of the new closed loop realizes fast and effective auto-searching least closed loops , which is proved to be effective by some leveling results of water census in Zhabei district of Shanghai city.
Key words: the least closed loop; the spanning tree; automatic searching; algorithm
在测量的数据处理中，为保证平差结果的正确
性，防止观测值可能含有粗差及系统误差影响平差结果，无论是导线网、水准网，还是GPS控制网，都需要对控制网中的各种多边形进行闭合差检核，以探测、剔除粗差，并评定观测值的质量1].最小独立团合环的确定是这一工作得以展开的首要工作，通常通过手工方法虽然也能完成闭合环的确定，但对于较为复杂的网型而言，这种方法容易出错，且不易做到最小性与独立性，而且数据处理时其效率较为低下，不能满足高质、高效的要求.因此，在进行最小独立团合环搜索时，利用计算机实现最小独立闭合环的自动生成在数据处理中具有重要意义
利用计算机进行最小独立闭合环的搜索时一般有以下几种方法：李光炎等12闸释了基于邻接矩阵变换的闭合环搜索算法；白征东[3给出了基于深
收稿日期：2017-02-13
作者简介：谢（1983－），男，江西吉安人，工程师，研究方向为工程测量变包数据
度优先的闭合环搜索算法；吕光帽14]将网型信息简化为拓扑图，利用图论的相关算法知识进行搜索；姚连壁(3利用网型信息构建一生成树，同时得到余枝信息，然后以余枝为基础搜索最小独立闭合环；赵一晗等确定了基于邻接矩阵的搜索算法.这些方法虽然都实现了最小独立闭合环的自动搜索，但其各具优缺点：基于邻接矩阵的押索算法虽然简单，但其时间复杂性与空间复杂性高，导致其计算时间长、效率较低；基于深度优先算法，在采用邻接表后，虽节省时间和空间，但在判断两端点是否直连时，不太方便；对于利用图论的相关算法进行搜索，编程复杂，不易实现：基于生成树和余树搜索算法虽然理论简单，但该搜索算法还可以进一步优化
本文是基于生成树和余树搜索算法，利用二维
数组存储结构，将原先由余枝一端先搜索闭合环、再判断选择的基本思路，改为由余枝两端司时搜索对方端点，遇同名点即得最小闭合环，最后再通过