c++ - 深度优先搜索树边缘分类

Question

我有一个关于 DFS 边缘分类的基本问题：我有一个带边的有向图：1->2、2->3 和 1->3。1->2 的边分类为树边，2->3 为树边。我对 1->3 的分类是什么感到困惑：前缘、后缘还是树缘？

Answer 1

根据边缘分类的定义（参见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 直接和通过 2 都是 1 的后代。