查找屬於簡單循環一部分的所有頂點

有沒有辦法在線性時間內找到屬於圖中簡單循環一部分的所有頂點？查找屬於簡單循環一部分的所有頂點

我在O（| V |（| V | + | E |））時發現了一種方法，但想知道是否有辦法更快地完成它？

來源

2013-07-05 Amnon

可能[重複]（http://cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph）？ –

我不明白你到底在問什麼。你給了一個簡單的循環，並且必須找到它的頂點？這個週期是如何規定的？你是否給出了一個圖表，並且必須過濾掉某個週期內沒有的頂點？ –

給定一個圖G =（V，E），找到一組頂點U，使得屬於U的每個頂點u都是一個簡單循環上的頂點 – Amnon

你想要做的是刪除所有Bridges（即刪除時斷開組件的邊緣）。維基百科的文章給出了一個線性時間算法來尋找所有的橋樑。

一旦所有的網橋都消失了，每個節點都是孤立的（具有度0）或者是週期的一部分。扔掉孤獨的節點，剩下的就是你想要的節點。

來源

2013-07-05 20:56:29

@DavidRicherby現在已經修復。 –

使用DFS（深度優先搜索），您可以在O（| V | + | E |）時間執行操作。在實現DFS時，只要保持你父節點跟蹤的verten的記錄，只要你找到了和父節點相同的父節點（意思是循環的完成），你可以聲明所有從那個父節點到最後一個孩子的節點作爲一些簡單循環的一部分。

以下評論如果您需要更多解釋。

來源

2013-07-05 10:19:00

這不是一個**簡單循環**，這僅僅是一個**循環**。簡單的循環不應包含任何其他循環。 –

這是我想到的算法，但我認爲如果很長時間我找到一個已經訪問過的頂點跟蹤它的所有前輩，我可以| V |圓圈（圓圈的一部分，屬於圓圈的一部分））和每一個O（| V |）時間爲此回溯。這與O（| V |（| V | + | E |））相加 – Amnon

我喜歡Bhavya的回答：但是如果我詳細說明它會有所幫助。

通常情況下，如果你做DFS你有一個訪問過的數組，保存訪問/未訪問狀態。

現在有

int visited[N];//N is the number of nodes/vertices in graph

讓

visited[i] =-1 if i-th vertex is not yet visited 
visited[i] = 0 if i-th vertex is being processed 
visited[i] = 1 if processing of i-th vertex is done

這樣，如果你遇到一個頂點一起參觀值0 DFS，它意味着你有一個cycle.To找到關於週期的頂點，使用前置數組將前一個頂點存儲在路徑中。

來源

2013-07-05 11:01:28 Aravind

好吧，我想我有答案。在處理DFS時，對於每個頂點v計算低（v）（下面解釋）。然後再次運行DFS和檢查每一個頂點v：

如果低（V）= d（V）（其中d（五）從DFS樹根的距離）

！頂點v是簡單循環的一部分。

*低（V）=分鐘（d（V），d（U），低（W）），其中（V，U）是後邊緣且w爲v的在一個子DFS樹。以O（| V | + | E |）時間計算。

來源

2013-07-06 08:06:50 Amnon

查找屬於簡單循環一部分的所有頂點

回答

相關問題