DFS強連通組件困境

問題：將問題1中圖的頂點集劃分爲強連通組件（SCC）。也就是說，指定第一個強連接組件中的哪個頂點，其中第二個爲，以此類推。DFS強連通組件困境

是否有人能夠確認我做到了這一點？即當我到達頂點4時，我可以選擇使第一個SCC爲1,7,2,4,3（如圖所示）或1,7,2,4,6,5，這取決於我選擇哪種方式旅行。有沒有一種方法，或者我可以簡單地選擇？

順序：

1,2,7,3,4,5,8,6

SCC：

1,7,2， 4,3

來源

2016-11-03 101ldaniels

錯誤ID最低restsrt。你怎麼能從7不到4的4？ {1,7,2,4,6,5}根本不是SCC。我認爲唯一的SCC是{1,2,3,4,5,6,7} – shole

@shole是的抱歉，我沒有先在反轉圖上預製dfs。所以強烈連接的組件是8和1,2,3,4,5,6,7 – 101ldaniels

的強連接組分是{1,2,3,4,5,6,7}。如果你沒有得到，你的算法（或你的實現）有一個錯誤。有一個強連通組件的定義，以及一些衆所周知的算法;在維基百科（以及許多其他互聯網資源）中都可以輕鬆找到這兩種文本，並且很可能在您的教科書和/或課程筆記中找到。（如果你沒有課程筆記，你可以很容易地找到一些類似的課程。）

來源

2016-11-03 03:05:57 rici

ahhh是的，我明白了。我沒有首先在反轉圖上預製dfs。乾杯！ – 101ldaniels

你可以添加5和6到1,7,2,4,3，因爲兩者都可以從其他人通過4

在DFS 你必須繼續visting節點和創建樹，而堆棧不爲空如果是這樣，然後用這仍然是白色

來源

2016-11-03 03:09:38

DFS強連通組件困境

回答

相關問題