[發明專利]一種有向圖中所有連通子圖的快速生成方法

在審

• 申請號: 201710359629.9
• 申請日: 2017-05-19
• 公開（公告）號: CN107193942A
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 舒新峰;馬青吉
• 申請（專利權）人: 西安郵電大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/50
• 代理公司: 西安長和專利代理有限公司61227
• 代理人: 黃偉洪

技術領域

本發明屬于軟件設計技術領域，尤其涉及一種有向圖中所有連通子圖的快速生成方法。

背景技術

圖作為一種非線性結構，應用非常廣泛，不僅局限于數學和計算機學科,還涵蓋了社會學、交通管理、系統工程、控制工程、通訊網絡等領域。圖的連通子圖在一些領域也得到了廣泛應用，例如，在面向對象軟件測試中，為了確定類的測試次序，需要求出類圖的所有連通子圖(回路)；利用信號流圖或流圖分析電子電路或反饋系統時，為了將電路、系統或計算機程序進行最優分解而尋找有向圖的最小反饋點(邊)集時，需要求出有向圖的全部連通子圖(回路)。圖指的是一個二元組(V，E)，其中V是圖的頂點集，E是圖的弧集，如果e∈E是有方向的，則稱其為有向弧。每條弧都有方向的圖稱為有向圖。圖中從頂點v₀到頂點v_m的路徑是一個有序頂點序列S＝{v₀,...,v_m}，其中頂點序列應滿足<v_j-1,v_j>∈E(1≤j≤m)。若且v_i≠v_j，則稱此路徑為簡單路徑；若<v_m,v₀>∈E，則稱序列S為連通子圖(回路)；特別的,如果且v_i≠v_j，<v_m,v₀>∈E，稱序列S是簡單連通子圖(簡單回路)。

已有的涉及有向圖的連通子圖的生成方法分為兩類，分別是求有向圖的極大連通子圖(強連通分量)和簡單連通子圖的。一種與本發明接近的求有向圖簡單連通子圖的生成方法的基本思想是：將有向圖中的n個頂點進行排序，例如n個頂點從小到大排序為1,…,n；然后，基于圖的深度優先搜索，依次從頂點1,2,…,n出發，向頂點序號大于出發頂點的方向進行遍歷，遍歷過程中采用數組p存儲簡單路徑，鏈表path[u]記錄每個頂點u到出發頂點v的路徑，通過判斷當前訪問頂點u是否是出發頂點v，或者u與v之間是否有路徑的方法計算有向圖的連通子圖，但由于通過該方法獲得的連通子圖的頂點均不相同，并且需要進行n次深度優先遍歷，故該方法只能計算出有向圖的簡單連通子圖，并且計算效率不高。

在交通領域，可以通過計算有向圖簡單連通子圖的方法查詢哪些城市之間有往返路線，例如通過計算有向圖簡單連通子圖的方法，可以知道北京到上海有往返路線，上海到天津有往返路線，但是沒有直接計算出北京到天津是否有往返路線。

綜上所述，現有技術存在的問題是：目前有向圖所有連通子圖的生成方法存在只能生成有向圖的極大連通子圖或者只能生成有向圖的簡單連通子圖，沒有生成有向圖所有連通子圖的方法。與本發明最接近的方法只能計算出有向圖的所有簡單連通子圖，并且在計算有向圖所有簡單連通子圖的過程中，需要進行n次深度優先遍歷，在處理復雜有向圖時算法效率低下。

發明內容

針對現有技術存在的問題，本發明提供了一種有向圖中所有連通子圖的快速生成方法。

本發明是這樣實現的，一種有向圖中所有連通子圖的快速生成方法，所述有向圖中所有連通子圖的快速生成方法基于圖的深度優先遍歷，遍歷過程中，將未被訪問的頂點壓入棧S中即借助棧S存儲有向圖的簡單路徑，若當前頂點v已被訪問，則判斷v是否在棧中，若是，根據棧S中簡單路徑，計算有向圖的簡單連通子圖；否則，若v在已獲得的簡單連通子圖中，則通過判斷棧中簡單路徑和已有簡單連通子圖是否有重合部分，計算可能存在的簡單連通子圖；根據所有簡單連通子圖，基于求集合冪集的方法，判斷簡單連通子圖之間是否有重合部分，對有重合部分的簡單連通子圖進行合并，計算有向圖的連通子圖，最終生成有向圖的所有連通子圖。

進一步，所述有向圖中所有連通子圖的快速生成方法包括以下步驟：

步驟一，選擇有向圖中一個未被訪問的頂點v；

步驟二，將v壓入棧S中；

步驟三，判斷v是否有鄰接頂點，若有，選擇v的第一個鄰接頂點w，否則，轉向步驟七；

步驟四，判斷w是否已經被訪問過，若未被訪問過，令v＝w，轉向步驟二；