Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Back edges in a graph

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.enter image description here

like image 317
Vlad Iordache Avatar asked Jun 12 '17 08:06

Vlad Iordache


People also ask

What is back edge and forward edge?

A forward edge is a non-tree edge from a vertex to one of its descendants. A cross edge is an edge from a vertex u to a vertex v such that the subtrees rooted at u and v are distinct. A back edge is an edge from a vertex to one of its ancestors.

What is back edge and tree edge?

Tree Edge: It is an edge that is present in the tree obtained after performing DFS on the graph. All the Green edges are tree edges as shown in the below image. Back Edge: It is an edge (u, v) such that v is an ancestor of node u but not part of the DFS Traversal of the tree.

How do you find the edge back on a directed graph?

To detect a back edge, keep track of vertices currently in the recursion stack of function for DFS traversal. If a vertex is reached that is already in the recursion stack then there is a cycle in the tree.

What are the edges of a graph called?

A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines).


2 Answers

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

enter image description here

like image 55
Sandipan Dey Avatar answered Oct 18 '22 02:10

Sandipan Dey


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

enter image description here

like image 37
gue Avatar answered Oct 18 '22 03:10

gue