深度优先搜索树边缘分类

我有一个关于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

回答