通过DFS确定有向图的后边缘不一致

Question

我发现了多种算法，可以使用DFS确定有向图的后边缘。不幸的是，我在所分析的一张图中发现不一致。请在下面找到一个最小的示例：

对于此有向图，我希望算法能确定仅一个后边缘，即我用红色标记的后边缘：E->B。

相反，根据我的理解，算法可以将边缘B->E确定为后边缘。不同的结果取决于图形的遍历，例如：

Traversal     | Back Edge
-------------------------
A->B->D->E    | E->B
A->C->D->E->B | B->E

Q1：假设图形的后边缘仅为E->B，是否正确？

Q2：如果是，哪种算法可以保证正确的DFS遍历？

Answer 1

回答Q1：否。由于后边缘取决于DFS树。

后边缘的定义：给定图的DFS树，后边缘是从节点到DFS树中其祖先之一的边缘。换句话说，后边缘是将顶点连接到在其父对象之前访问过的顶点的边缘。

根据邻接表中节点的顺序或您决定访问这些节点的顺序，可能有多个DFS树。

因此，对于particular DFS tree -> Unique set of back edges。

回答问题2：如上所述，没有正确的DFS遍历。同一棵树或图形可以存在多个DFS遍历。