0、什么是環？

在圖論中，環（英語：cycle）是一條只有第一個和最后一個頂點重復的非空路徑。

在有向圖中，一個結點經過兩種路線到達另一個結點，未必形成環。

1、拓撲排序

1.1、無向圖

使用拓撲排序可以判斷一個無向圖中是否存在環，具體步驟如下：

1. 求出圖中所有結點的度。
2. 將所有度 <= 1 的結點入隊。（獨立結點的度為 0）
3. 當隊列不空時，彈出隊首元素，把與隊首元素相鄰節點的度減一。如果相鄰節點的度變為一，則將相鄰結點入隊。
4. 循環結束時判斷已經訪問的結點數是否等于 n。等于 n 說明全部結點都被訪問過，無環；反之，則有環。

1.2、有向圖

使用拓撲排序判斷無向圖和有向圖中是否存在環的區別在于：

• 在判斷無向圖中是否存在環時，是將所有**度 <= 1** 的結點入隊；
• 在判斷有向圖中是否存在環時，是將所有**入度 = 0** 的結點入隊。（感謝 wangweijun@shen 指正！！！）

2、DFS

使用 DFS 可以判斷一個無向圖和有向中是否存在環。深度優先遍歷圖，如果在遍歷的過程中，發現某個結點有一條邊指向已訪問過的結點，并且這個已訪問過的結點不是上一步訪問的結點，則表示存在環。

我們不能僅僅使用一個 bool 數組來表示結點是否訪問過。規定每個結點都擁有三種狀態，白、灰、黑。開始時所有結點都是白色，當訪問過某個結點后，該結點變為灰色，當該結點的所有鄰接點都訪問完，該節點變為黑色。

那么我們的算法可以表示為：如果在遍歷的過程中，發現某個結點有一條邊指向灰色節點，并且這個灰色結點不是上一步訪問的結點，那么存在環。

#include 

3、Union-Find Set

我們可以使用并查集來判斷一個圖中是否存在環：

對于無向圖來說，在遍歷邊（u-v）時，如果結點 u 和結點 v 的“父親”相同，那么結點 u 和結點 v 在同一個環中。

對于有向圖來說，在遍歷邊（u->v）時，如果結點 u 的“父親”是結點 v，那么結點 u 和結點 v 在同一個環中。

#include 

References

1. 環 (圖論)
2. 有向無環圖
3. 判斷一個圖是否有環及相關 LeetCode 題目
4. 判斷有向圖是否存在環的 2 種方法（深度遍歷，拓撲排序）

總結

以上是生活随笔為你收集整理的jquery判断方法是否存在_判断图中是否有环的三种方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。