Back edges in a graph
...a Back Edge is an edge that connects a vertex to a vertex that is discovered before it's parent.
from your source.
Think about it like this: When you apply a DFS on a graph you fix some path that the algorithm chooses. Now in the given case: 0->1->2->3->4
. As in the article mentioned, the source graph contains the edges 4-2
and 3-1
. When the DFS reaches 3 it could choose 1 but 1 is already in your path so it is a back edge
and therefore, as mentioned in the source, a possible alternative path.
Addressing your second question: Are 2-1, 3-2, and 4-3 back edges too? For a different path they can be. Suppose your DFS chooses 0->1->3->2->4
then 2-1
and 4-3
are back edges.
In essence, when you do a DFS, if there are cycles in your graph between nodes A, B and C and you have discovered the edges A-B, later you discover the edge B-C, then, since you have reached node C, you will discover the edge C-A, but you need to ignore this path in your search to avoid infinite loops. So, in your search A-B and B-C were not back edges, but C-A is a back edge, since this edge forms a cycle back to an already visited node.