[發明專利]基于廣度優先搜索算法的管網空間分析方法

在審

• 申請號: 201510648981.5
• 申請日: 2015-10-09
• 公開（公告）號: CN105225187A
• 公開（公告）日: 2016-01-06
• 發明（設計）人: 楊俊;魯雪松;汪小東;曾書昶;鈕立明;陳建偉
• 申請（專利權）人: 蘇州盛景信息科技股份有限公司
• 主分類號: G06Q50/26
• 分類號: G06Q50/26;G06F17/30
• 代理公司: 蘇州慧通知識產權代理事務所(普通合伙) 32239
• 代理人: 黃建月

1.一種基于廣度優先搜索算法的管網空間分析方法，其特征在于，所述方法包括：以源點V0向外擴展，首先訪問到的距離為K，未被訪問的鄰接頂點為V1，V2，V3，······Vn，再以這些頂點為中心，訪問與源點V0距離為K+1的其他未被訪問的頂點，直到全部頂點被訪問完為止，其中，n為大于1的整數，以實現管網的連通分析、爆管分析、最短路徑分析和剖面分析。

2.根據權利要求1所述的管網空間分析方法，其特征在于，所述廣度優先搜索算法包括記錄路徑的連通分析算法、排除可關可不關閥門的爆管分析算法、最短路徑算法以及剖面分析算法。

3.根據權利要求2所述的管網空間分析方法，其特征在于，所述連通分析方法中，將管網中的所有頂點分為已經搜索過的頂點、即將搜索的鄰接頂點、從未遍歷的頂點，所述連通分析方法的過程包括：

步驟1，輸入起點V0，并將所述起點V0加入即將搜索的鄰接頂點序列；

步驟2，判斷即將搜索的鄰接頂點序列中是否有值，若有，則從所述即將搜索的鄰接頂點序列中取出一個頂點Vn，將頂點Vn加入所述已經搜索過的頂點序列中，并取出頂點Vn所有上游相鄰且未被訪問的頂點Vw，將Vn和Vw記錄到路徑；

步驟3，判斷是否有終點V1，若有，則繼續進入步驟2，若沒有，則將頂點Vw加入即將搜索的鄰接頂點序列中，并進入步驟2。

4.根據權利要求3所述的管網空間分析方法，其特征在于，步驟2中，若即將搜索的鄰接頂點序列中沒有值，則判斷是否找到目標點，若找到，則保留路徑并結束遍歷，若未找到，則清空路徑并結束遍歷。

5.根據權利要求2所述的管網空間分析方法，其特征在于，所述爆管分析算法通過獲取閥門點集合V，然后對其進行判斷分析，進行排除，設V＝{V0，V1，V2……Vn}，若V0在下游存在一個或多個閥門，則V1、V2……Vn為可關可不關閥門，所述爆管分析算法包括：

起始點為V中閥門點，采用廣度優先搜索算法搜索其下游節點，若此節點屬于集合V，將其移出集合V添加到可關可不關閥門集合VA中，并將起始點的下游最近閥門列入可關可不關閥門。

6.根據權利要求2所述的管網空間分析方法，其特征在于，所述最短路徑分析算法采用單源最短路徑算法計算管網有向圖中兩個頂點的最短路徑。

7.根據權利要求2所述的管網空間分析方法，其特征在于，所述剖面分析算法包括橫剖面分析算法和縱剖面分析算法。