[發明專利]用于驗證有向無環圖的環的方法及裝置、電子設備、存儲介質

在審

• 申請號: 202110963189.4
• 申請日: 2021-08-20
• 公開（公告）號: CN113672369A
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 王培梁
• 申請（專利權）人: 北京明略軟件系統有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F16/901;G06F16/903
• 代理公司: 北京康盛知識產權代理有限公司 11331
• 代理人: 陶俊潔

本申請涉及有向無環圖技術領域，公開一種用于驗證有向無環圖的環的方法，通過獲取有向無環圖中未入棧的多個節點，從中選取一個節點為起始節點，并對起始節點對應的多條路徑依次進行遍歷，對待遍歷路徑執行第一預設操作，即從待遍歷路徑中的第一個待遍歷節點開始依次對待遍歷路徑中的節點執行第二預設操作，在各節點均執行完第二預設操作且未確定出有向無環圖存在閉環的情況下，將待遍歷路徑中的待遍歷節點均出棧；在各路徑均執行完第一預設操作且未確定出有向無環圖存在閉環的情況下，確定有向無環圖不存在閉環。這樣，能夠提高判斷有向無環圖是否存在閉環的效率。本申請還公開一種用于驗證有向無環圖的環的裝置、電子設備、存儲介質。

技術領域

本申請涉及有向無環圖技術領域，例如涉及一種用于驗證有向無環圖的環的方法及裝置、電子設備、存儲介質。

背景技術

有向無環圖指的是一個無回路的有向圖，其被越來越多的運用于工作中，例如：在調度系統的任務可視化界面，需要用戶在任務可視化界面連線作為兩個任務之間的依賴關系，這些任務之間即構成有向無環圖。在添加依賴關系時，需要先判斷該連線是否與已存在的依賴關系形成閉環，如果存在閉環，就會使調度系統陷入死循環，任務不能正常執行。因此，判斷有向無環圖是否存在閉環至關重要。

在實現本公開實施例的過程中，發現相關技術中至少存在如下問題：

現有技術中通常采用鄰接矩陣的方式來判斷有向無環圖是否有環，這種判斷有向無環圖是否存在閉環的方法的效率較低。

發明內容

為了對披露的實施例的一些方面有基本的理解，下面給出了簡單的概括。所述概括不是泛泛評述，也不是要確定關鍵/重要組成元素或描繪這些實施例的保護范圍，而是作為后面的詳細說明的序言。

本公開實施例提供了一種用于驗證有向無環圖的環的方法及裝置、電子設備、存儲介質，以提高判斷有向無環圖是否存在閉環的效率。

在一些實施例中，用于驗證有向無環圖的環的方法，包括：獲取有向無環圖中的多個節點，各所述節點的入棧狀態均為未入棧；從各所述節點中選取一個節點為起始節點，并對所述起始節點進行入棧操作；獲取所述起始節點對應的多條路徑；所述路徑中的節點包括起始節點和待遍歷節點，所述路徑中各節點通過有向邊順序連接；所述待遍歷節點為起始節點外的其他節點；從多條所述路徑中依次選取一條路徑確定為待遍歷路徑，對所述待遍歷路徑執行第一預設操作；所述第一預設操作為確定所述待遍歷路徑中的第一個待遍歷節點，并從所述第一個待遍歷節點開始根據所述待遍歷路徑的有向邊依次對所述待遍歷路徑中的節點執行第二預設操作，在所述待遍歷路徑中的節點均執行完第二預設操作且未確定出所述有向無環圖存在閉環的情況下，將所述待遍歷路徑中的待遍歷節點均出棧；所述第二預設操作為判斷節點的入棧狀態，在入棧狀態為未入棧的情況下對節點進行入棧操作，在入棧狀態為已入棧的情況下確定所述有向無環圖存在閉環；在各所述路徑均執行完第一預設操作且未確定出所述有向無環圖存在閉環的情況下，則確定所述有向無環圖不存在閉環。