夏先勤

（安徽理工大學空間信息與測繪工程學院，安徽 淮南 232001）

水準網(wǎng)路線環(huán)閉合差自動檢核的第一步是找到最小獨立閉合環(huán)[1]。實現(xiàn)最小獨立閉合環(huán)自動搜索的主要思想可以歸納為4類：基于生成樹和余樹的思想[2]、基于深度優(yōu)先的思想[3]、基于廣度優(yōu)先的思想[4]、基于鄰接矩陣變換的思想[5]。本文詳細闡述了基于廣度優(yōu)先的最小獨立閉合環(huán)搜索算法，并在此基礎上采用Python（計算機編程語言）實現(xiàn)了水準網(wǎng)最小獨立閉合環(huán)搜索及其閉合差檢核的程序設計。

1 基于廣度優(yōu)先的最小獨立閉合環(huán)搜索

基于廣度優(yōu)先的最小獨立閉合環(huán)搜索在更新鄰接點集合時將記錄所有的鄰接點，而不會判斷鄰接點是否被訪問過[6]。以從無向圖G中搜索以頂點v1，v2，v3組成的最小獨立閉合環(huán)為例（見圖1），本文基于廣度優(yōu)先搜索的思想來實現(xiàn)最小獨立閉合環(huán)搜索的主要過程描述如下。

圖1 無向圖G

步驟一：在圖中選擇起始頂點v1，搜索層次k=1，搜索得到k=1層根節(jié)點v1的所有鄰接點組成的集合為

步驟二：搜索層次k=2，搜索得到k=2層根節(jié)點v2，v3，v5的鄰接點并將鄰接點集合更新為

在每個子集中刪除k=1層根節(jié)點，得到鄰接點集合為

步驟三：搜索層次k=3，以步驟二中搜索到的3個鄰接點子集為基礎，搜索得到k=3層根節(jié)點v2，v3，v4，v6的鄰接點并將鄰接點集合更新為

其中v2/v3表示v2或v3，v3/v5同理。

步驟四：此時n≥3，判斷是否形成最小獨立閉合環(huán)：步驟三所得到的集合的子集中，集合v1:v2:v3:{v1，v2，v4，v6}與集合v1:v3:v2:{v1，v3，v4}都包含有k=1層根節(jié)點v1；提取各層根節(jié)點組成集合{v1，v2，v3}，此時認為搜索到了最小獨立閉合環(huán)，最小獨立閉合環(huán)的頂點即為v1，v2，v3。

2 基于Python的程序設計

2.1 水準網(wǎng)數(shù)據(jù)的組織

將原始水準網(wǎng)數(shù)據(jù)存儲在“.txt”文件中，已知點數(shù)據(jù)以“#”開頭作為標記；示例中已知點為F，其高程為11.414 m。已知點數(shù)據(jù)之后為測段數(shù)據(jù)，以第一個測段為例， “A”為測段后視點， “B”為測段前視點， “73.795”為測段高差（單位：m），“20.400”為測段長度（單位：m）。水準網(wǎng)數(shù)據(jù)格式示例如下。

采用Python內置的 “.readlines()”函數(shù)將文本文件讀取到列表中，然后對列表中的每一行采用“.strip()”函數(shù)截取掉所有的回車字符，進而采用“.split(‘ ’)”將得到的整行數(shù)據(jù)分割成元素列表。最終讀取到程序中的水準網(wǎng)數(shù)據(jù)以二維列表的形式存儲，二維列表中的子列表按順序對應著文本文件中的某一行。以水準網(wǎng)數(shù)據(jù)格式示例中的前三行數(shù)據(jù)為例，程序讀取后會將其存儲為二維列表：[[‘F’，11.414]，[‘A’， ‘B’，73.795，20.400]，[‘A’， ‘D’，14.005，18.800]]。

2.2 程序算法

程序實現(xiàn)的基本框架是基于廣度優(yōu)先的最小獨立閉合環(huán)搜索算法，但如果在程序實現(xiàn)過程中僅采用基于廣度優(yōu)先的最小獨立閉合環(huán)搜索的話，在某些特殊情況下會遺漏最小獨立閉合環(huán)[7]。以無向圖G′的最小獨立閉合環(huán)搜索為例（見圖2），采用基于廣度優(yōu)先的最小獨立閉合環(huán)搜索算法進行搜索時，無論是以{v1，v2，v3，v4，v5，v6，v7，v8}哪一個結點作為搜索的起始頂點，都只能搜索到{{v1，v5，v6},{v2，v6，v7},{v3，v7，v8},{v4，v5，v8}}這4個最小獨立閉合環(huán)中的一個，而中間四頂點的最小獨立閉合環(huán){v5，v6，v7，v8}將被遺漏[8]。

圖2 無向圖G'

為此，本文在具體程序實現(xiàn)時在基于廣度優(yōu)先的最小獨立閉合環(huán)搜索算法中嵌入“深度搜索”的過程[9]，這一過程僅在當前搜索到的最小獨立閉合環(huán)已經(jīng)存在的情況下執(zhí)行。進行“深度搜索”的具體流程見圖3。

圖3 深度搜索流程圖

3 實例驗證

為驗證本文中所設計的算法的正確性與有效性，選取某次工程應用中的二等水準網(wǎng)實例數(shù)據(jù)對其進行測試[10]。所選取的水準網(wǎng)共有21個水準點，37個測段，其中BM1，BM2，BM3，BM4與BM5為已知點，見圖4。

圖4 二等水準網(wǎng)實例

通過自編程序對數(shù)據(jù)進行處理，成功搜索到全部的17個最小獨立閉合環(huán)，經(jīng)檢核，水準網(wǎng)中最小獨立閉合環(huán)的環(huán)線閉合差均滿足二等水準測量的要求。運行程序的計算機配置為Intel酷睿i5-8250U CPU，內存頻率為2 133 MHz，平均運行時間為0.01 s。為了進一步驗證搜索結果，采用傳統(tǒng)的COSA軟件進行閉合差檢核也得到了相同的結果。

4 結束語

本文提出了基于廣度優(yōu)先的最小獨立閉合環(huán)搜索算法，針對基于單一的廣度優(yōu)先進行最小獨立閉合環(huán)搜索時可能會遺漏最小獨立閉合環(huán)的問題，在廣度優(yōu)先搜索中嵌入了“深度搜索”的過程，最后的實例驗證表明本文提出的算法能夠在較短的時間內正確搜索并完成水準網(wǎng)的環(huán)閉合差檢核工作。只要稍加改進，這一算法同樣也能夠應用于GPS控制網(wǎng)和平面三角網(wǎng)的環(huán)閉合差檢核工作。