[發(fā)明專利]一種有向圖中的環(huán)路檢測方法、裝置、設(shè)備和存儲介質(zhì)

有效

• 申請?zhí)枺?/td>: 201911328366.0
• 申請日: 2019-12-20
• 公開（公告）號: CN110968429B
• 公開（公告）日: 2022-11-11
• 發(fā)明（設(shè)計）人: 盧文祥;李玉明;王云龍;周力;蔡歌;汪洋;袁鵬程;李剛
• 申請（專利權(quán)）人: 北京百度網(wǎng)訊科技有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F16/901
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆

本申請公開了一種有向圖中的環(huán)路檢測方法、裝置、設(shè)備和存儲介質(zhì)，涉及圖論技術(shù)領(lǐng)域。具體實現(xiàn)方案為：分布式集群中的服務(wù)中心獲取待檢測的有向圖；服務(wù)中心對有向圖的至少一個邊進(jìn)行切割，得到多個子圖；服務(wù)中心將多個子圖分發(fā)至分布式集群中的多個計算節(jié)點，以供每個計算節(jié)點檢測接收到的子圖中的環(huán)路和鏈路；服務(wù)中心從多個計算節(jié)點獲取多個子圖中的環(huán)路和鏈路，并根據(jù)子圖之間的被切邊的信息，對獲取的環(huán)路和/或鏈路進(jìn)行拼接，得到有向圖中的環(huán)路。本申請實施例充分利用分布式集群的計算資源提高檢測效率；通過并行檢測子圖中的環(huán)路和鏈路，再對環(huán)路和鏈路進(jìn)行拼接，使得在提高檢測效率的同時，有效提高環(huán)路的檢出率。

技術(shù)領(lǐng)域

本申請涉及計算機(jī)技術(shù)，尤其涉及圖論技術(shù)領(lǐng)域。

背景技術(shù)

在基于有向圖的數(shù)據(jù)處理場景中，常常需要檢測其中的環(huán)路，以對環(huán)路中的數(shù)據(jù)進(jìn)行針對性處理。

目前，對有向圖的環(huán)路檢測普遍采用如下方式：深度優(yōu)先遍歷、廣度優(yōu)先遍歷和拓?fù)渑判颉Ｈ欢@三種檢測方式均采用頂點的串行遍歷方式。這種方式效率低下，一次遍歷耗時過長；而且不能保證所有環(huán)路的檢出。

發(fā)明內(nèi)容

本申請實施例提供了一種有向圖中的環(huán)路檢測方法、裝置、設(shè)備和存儲介質(zhì)，以提高有向圖中環(huán)路的檢出率，并提高檢測效率。

第一方面，本申請實施例提供了一種有向圖中的環(huán)路檢測方法，包括：

分布式集群中的服務(wù)中心獲取待檢測的有向圖；

所述服務(wù)中心對所述有向圖的至少一個邊進(jìn)行切割，得到多個子圖；

所述服務(wù)中心將多個子圖分發(fā)至分布式集群中的多個計算節(jié)點，以供每個計算節(jié)點檢測接收到的子圖中的環(huán)路和鏈路；

所述服務(wù)中心從多個計算節(jié)點獲取多個子圖中的環(huán)路和鏈路，并根據(jù)子圖之間的被切邊的信息，對獲取的環(huán)路和/或鏈路進(jìn)行拼接，得到所述有向圖中的環(huán)路。

本申請實施例將環(huán)路檢測方法應(yīng)用于分布式集群中，通過其中的服務(wù)中心切割得到子圖，再由多個計算節(jié)點并行檢測子圖中的環(huán)路和鏈路，再通過服務(wù)中心拼接子圖中的環(huán)路和鏈路，最終得到有向圖中的環(huán)路，充分利用分布式集群的計算資源提高檢測效率，面對巨大圖的大量環(huán)計算時，執(zhí)行效率提高20％-30％；而且，無需標(biāo)定初始頂點或者入口頂點，即可以實現(xiàn)有向圖的環(huán)路的盲檢測；通過并行檢測子圖中的環(huán)路和鏈路，再對環(huán)路和鏈路進(jìn)行拼接，使得在提高檢測效率的同時，不再依賴于頂點的串行遍歷方式，而是依賴于環(huán)路和鏈路的拼接方式，即將小環(huán)路和鏈路拼接為大環(huán)路，由部分拼接為整體，這種方式能夠有效提高環(huán)路的檢出率。而且，對有向圖而言只需遍歷一次，序列組合階段可以脫離原圖，適用于動態(tài)找環(huán)的場景。

可選的，每個被切邊的兩個切割點順序構(gòu)成切邊序列，環(huán)路的各頂點順序構(gòu)成環(huán)序列，鏈路的各頂點順序構(gòu)成鏈序列；對于第一切邊序列，所述服務(wù)中心根據(jù)子圖之間的被切邊的信息，對獲取的環(huán)路和/或鏈路進(jìn)行拼接，得到所述有向圖中的環(huán)路，包括：

所述服務(wù)中心從獲取的環(huán)序列和鏈序列中，查找所述第一切邊序列的鄰接序列；

所述服務(wù)中心將所述鄰接序列與所述第一切邊序列拼接得到新的第一切邊序列；

如果新的第一切邊序列中不存在重復(fù)頂點，所述服務(wù)中心判斷新的第一切邊序列的首尾是否存在有向邊；

如果存在，所述服務(wù)中心將新的第一切邊序列檢測為所述有向圖中的環(huán)路。

可選的，上述方法還包括：如果不存在，所述服務(wù)中心從獲取的環(huán)序列和鏈序列中剔除所述鄰接序列，返回執(zhí)行鄰接序列的查找操作，直到新的第一切邊序列包括所述有向圖中的全部頂點，或者未找到鄰接序列。