Back edges in a graph

Question

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.

Answer 1

Consider the following (directed) graph traversal with DFS. Here the colors of the nodes represent the following:

1. The floral-white nodes are the ones that are yet to be visited
2. The gray nodes are the nodes that are visited and on stack
3. The black nodes are the ones that are popped from the stack.

Notice that when the node 13 discovers the node 0 through the edge 13->0 the node 0 is still on the stack. Here, 13->0 is a back edge and it denotes the existence of a cycle (the triangle 0->1->13).

Answer 2

...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.