深度優先搜索樹邊緣分類

我有一個關於DFS邊緣分類的基本問題：我有一個有邊緣的有向圖：1-> 2，2-> 3和1-> 3。 1-> 2的邊緣分類是樹邊緣，2-> 3是樹邊緣。我很困惑1-> 3的分類是：前沿，後沿還是樹邊緣？深度優先搜索樹邊緣分類

2013-05-10 chotu123

根據邊緣分類的定義（例如參見http://en.wikipedia.org/wiki/Depth-first_search），1-> 3將是前沿。

這將是因爲：
1-> 2：樹邊緣，因爲2是1和2的後代還沒有被發現。
2-> 3：樹邊緣因爲3是2和3的後代尚未被發現。
1-> 3：前沿，因爲3是1的後代並且已經被發現。

3是1直接或通過2

2013-05-10 19:36:49 GHC

只是想確認，是由於一些困惑的後代。謝謝！ – chotu123 2013-05-10 19:52:14

此答案不反映DFS的非確定性。如果源爲1，並且要發現的第一條邊是（1,3），則它是樹邊而不是前向邊，在這種情況下（1,2）也將是樹邊，而（2,3））將是一個前沿。 – 2013-05-11 00:01:32

@ G.Bach +1 Fair cop，guvnor。我假定節點訪問的順序是OP將它們列入的順序。我的答案可能更完整。助教。 – GHC 2013-05-11 08:13:19

回答