基于廣度優先的最小獨立閉合環搜索及其實現

夏先勤

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

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

1 基于廣度優先的最小獨立閉合環搜索

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

圖1 無向圖G

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

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

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

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

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

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

2 基于Python的程序設計

2.1 水準網數據的組織

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

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

2.2 程序算法

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

圖2 無向圖G'

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

圖3 深度搜索流程圖

3 實例驗證

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

圖4 二等水準網實例

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

4 結束語

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