I'm having a hard time understanding Tarjan's algorithm for articulation points. I'm currently following this tutorial here: https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/. What I really can't see, and couldn't see in any other tutorial, is what exactly a "back edge" means. Considering the graph given there, I know 3-1 and 4-2 are back edges, but are 2-1, 3-2, and 4-3 back edges too? Thank you.
...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.