[發(fā)明專(zhuān)利]一種有向圖中所有連通子圖的快速生成方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710359629.9
• 申請(qǐng)日: 2017-05-19
• 公開(kāi)（公告）號(hào): CN107193942A
• 公開(kāi)（公告）日: 2017-09-22
• 發(fā)明（設(shè)計(jì)）人: 舒新峰;馬青吉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安郵電大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30;G06F17/50
• 代理公司: 西安長(zhǎng)和專(zhuān)利代理有限公司61227
• 代理人: 黃偉洪

1.一種有向圖中所有連通子圖的快速生成方法，其特征在于，所述有向圖中所有連通子圖的快速生成方法基于圖的深度優(yōu)先遍歷，遍歷過(guò)程中，將未被訪問(wèn)的頂點(diǎn)壓入棧S中即借助棧S存儲(chǔ)有向圖的簡(jiǎn)單路徑，若當(dāng)前頂點(diǎn)v已被訪問(wèn)，則判斷v是否在棧中，若是，根據(jù)棧S中簡(jiǎn)單路徑，計(jì)算有向圖的簡(jiǎn)單連通子圖；否則，若v在已獲得的簡(jiǎn)單連通子圖中，則通過(guò)判斷棧中簡(jiǎn)單路徑和已有簡(jiǎn)單連通子圖是否有重合部分，計(jì)算可能存在的簡(jiǎn)單連通子圖；根據(jù)所有簡(jiǎn)單連通子圖，基于求集合冪集的方法，判斷簡(jiǎn)單連通子圖之間是否有重合部分，對(duì)有重合部分的簡(jiǎn)單連通子圖進(jìn)行合并，計(jì)算有向圖的連通子圖，最終生成有向圖的所有連通子圖。

2.如權(quán)利要求1所述的有向圖中所有連通子圖的快速生成方法，其特征在于，所述有向圖中所有連通子圖的快速生成方法包括以下步驟：

步驟一，選擇有向圖中一個(gè)未被訪問(wèn)的頂點(diǎn)v；

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

步驟三，判斷v是否有鄰接頂點(diǎn)，若有，選擇v的第一個(gè)鄰接頂點(diǎn)w，否則，轉(zhuǎn)向步驟七；

步驟四，判斷w是否已經(jīng)被訪問(wèn)過(guò)，若未被訪問(wèn)過(guò)，令v＝w，轉(zhuǎn)向步驟二；

步驟五，判斷w是否在棧S＝<v₀,…,v_m>中，若在，即S＝<v₀,…,w,…,v_m>，根據(jù)棧S中簡(jiǎn)單路徑，計(jì)算有向圖的簡(jiǎn)單連通子圖scc＝<w,...,v_m>，將scc無(wú)重復(fù)添加至SCCSet中，轉(zhuǎn)向步驟八；

步驟六，判斷棧S中簡(jiǎn)單路徑和已獲得的簡(jiǎn)單連通子圖是否存在重合部分，計(jì)算可能存在的簡(jiǎn)單連通子圖，將計(jì)算得到的所有簡(jiǎn)單連通子圖依次無(wú)重復(fù)的添加至SCCSet中，轉(zhuǎn)向步驟八；

步驟七，令w＝Top(S)，S的棧頂頂點(diǎn)出棧，判斷棧S是否為空，若是，轉(zhuǎn)向步驟九；否則，令v＝Top(S)；

步驟八，判斷w是否是v的最后一個(gè)鄰接頂點(diǎn)，若是，轉(zhuǎn)向步驟七，否則，選擇v的相對(duì)于w的下一個(gè)鄰接頂點(diǎn)u，令w＝u，轉(zhuǎn)向步驟四；

步驟九，判斷有向圖所有頂點(diǎn)是否都被訪問(wèn)完，若沒(méi)有，轉(zhuǎn)向步驟一，否則，獲得有向圖所有簡(jiǎn)單連通子圖，并且所有簡(jiǎn)單連通子圖均存儲(chǔ)在SCCSet中；

步驟十，判斷SCCSet是否為空，若是，則有向圖無(wú)簡(jiǎn)單連通子圖，因此無(wú)連通子圖，結(jié)束；否則，根據(jù)所有簡(jiǎn)單連通子圖，生成有向圖的所有連通子圖，結(jié)束。

3.如權(quán)利要求2所述的有向圖中所有連通子圖的快速生成方法，其特征在于，所述有向圖的簡(jiǎn)單連通子圖用構(gòu)成簡(jiǎn)單連通子圖的有序頂點(diǎn)序列scc＝<v₀′,…,v_m′>表示，其中對(duì)于所有1≤j≤m，<v_j-1′,v_j′>∈E，且<v_m′,v₀′>∈E。