通过 DFS 确定有向图的后边时不一致
Inconsistency in determining directed graph's back edges via DFS
我发现了多种允许使用 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遍历正确？
Q1的回答：不是。因为后边依赖于DFS树。
Definition of back edge: Given a DFS tree of a graph, a back edge is an edge from a node to one of its ancestors in the DFS tree. In other words, a back edge is an edge that connects a vertex to a vertex that has been visited before it's parent.
根据邻接表中节点的顺序或您决定访问节点的顺序，可以有多个 DFS 树。
因此，对于 particular DFS tree -> Unique set of back edges.
问题 2 的回答： 正如所讨论的，没有一种正确的 DFS 遍历。同一个树或图可以存在多个 DFS 遍历。
我发现了多种允许使用 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遍历正确？
Q1的回答：不是。因为后边依赖于DFS树。
Definition of back edge: Given a DFS tree of a graph, a back edge is an edge from a node to one of its ancestors in the DFS tree. In other words, a back edge is an edge that connects a vertex to a vertex that has been visited before it's parent.
根据邻接表中节点的顺序或您决定访问节点的顺序，可以有多个 DFS 树。
因此，对于 particular DFS tree -> Unique set of back edges.
问题 2 的回答： 正如所讨论的，没有一种正确的 DFS 遍历。同一个树或图可以存在多个 DFS 遍历。