Search code examples
algorithmgraphgraph-algorithmdepth-first-searchdigraphs

Inconsistency in determining directed graph's back edges via DFS

I have found multiple algorithms that allows determining the back edges of a directed graph using DFS. Unfortunately, I found an inconsistency in one of the graphs I am analyzing. Please find below a minimal example:

enter image description here

For this directed graph, I expected the algorithms to determine only one back edge that is the one I marked in red: E->B.

Instead, differently from my understanding, the algorithms can determine as a back edge also edge B->E. The different results depend on the graph's traversals, for instance:

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

Q1: Is it correct assuming that the graph's back edge is only E->B?

Q2: If so, which algorithm can guarantee the correct DFS traversal?

Solution

  • Answer to Q1: No. As the back edges are dependant on the DFS tree.

    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.

    There can be multiple DFS trees possible based on the order of nodes in adjacency list or the order in which you decide to visit the nodes.

    Therefore, for a particular DFS tree -> Unique set of back edges.

    Answer to Q2: As discussed, there is no kind of correct DFS traversal. Multiple DFS traversal can exist for a same tree or graph.