如何檢查邊緣是否處於某個循環？

Question

我有一個hw問題，要求提供一種算法來檢測任何包含任何給定邊「E」的無向圖中是否有任何循環。該算法應該以O（N）的線性時間運行。

我遇到的問題是我不知道從哪裏開始。我有一些簡單的示例圖，但我不知道從哪裏去。

任何提示？

Answer 1

你從邊緣'e'開始。從它你應該得到它連接的兩個頂點。從它們中可以得到其他邊和其他頂點，以及其他邊和其他頂點，以及...您需要一種方法來確定頂點是否已被您的算法「訪問過」。如果它有一個'e'是其中一部分的週期。

Answer 2

進行深度優先搜索，隨時添加節點到列表中，並在返回時從列表中刪除它們。

該列表表示您當前的遍歷路徑。

如果你遇到一個已經在你的列表中的節點，那麼就有一個循環/循環。

Answer 3

對於邊（u，v）的：

1-執行從u開始的深度優先搜索，確定如果v是發現和後邊緣沿所述路徑到v存在

2-。執行從v的深度優先搜索，如果u是發現和後邊緣存在於U，然後有一個週期，其包括既u和v。

換句話說，

1-執行DFS從u開始，檢查後邊緣是否存在，v尚未完成。

2-執行從v開始的DFS，檢查後邊緣是否存在並且u還沒有完成 如果兩個條件都爲真，則邊（u，v）屬於一個循環。

Answer 4

取出G.的邊緣（u，v） 1.運行BFS以查看v是否仍可從u到達。 2.如果是，那麼原始圖形有一個包含e的循環。否則沒有。