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.

By convention, for undirected graphs, no. These are called tree edges, since they are part of the DFS tree. Back edges refer to _non-tree_ edges that go from a node u in the DFS tree to some ancestor w of u in the DFS tree. — Neal Young, Oct 25 '18 at 22:24

gue · Accepted Answer · 2017-06-12T08:33:45.520

15

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

edited Jun 12 '17 at 08:33

answered Jun 12 '17 at 08:26

gue

1,868
1
16
21

1

What you've shown above in Fig. 1 cannot be a DFS tree of an undirected graph, at least if you mean the tree edges to be (1, 0) (0, 5) (1, 2) (3, 4). Then (3, 2) and (4, 2) would be cross edges, which never arise in a DFS of an undirected graph. Also, in a _directed_ graph, an edge (u, w) that goes from a node u that the DFS is visiting to a node w that has already been discovered does not have to be a back edge. It can be a cross edge. – Neal Young Oct 25 '18 at 22:23

score 5 · Answer 2 · answered Oct 10 '20 at 21:02

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

The floral-white nodes are the ones that are yet to be visited
The gray nodes are the nodes that are visited and on stack
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).

score 4 · Answer 3 · answered Jun 12 '17 at 08:34

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.

score 1 · Answer 4 · answered Jun 12 '17 at 08:18

From article mentioned:

Given a DFS tree of a graph, a Back Edge is an edge that connects a vertex to a vertex that is discovered before it's parent.

2-1, 3-2, 4-3 are not "Back edge" because they link the vertices with their parents in DFS tree.

score -2 · Answer 5 · edited May 17 '21 at 10:15

Here is the code for a better understand:

#include<bits/stdc++.h>

using namespace std;

struct vertex{

    int node;

    int start;

    int finish;

    int color;

    int parent;

};


int WHITE=0, BLACK=1, GREY=2;

vector<int> adjList[8];

int num_of_verts = 8;
struct vertex vertices[8];

int t=0;

bool DFS_visit(int u){

    bool cycleExists = false;

    vertices[u].color=GREY;

    t++;

    vertices[u].start= t;


    for( int i=0;   adjList[u][i]!=-1; i++){

        if( vertices[adjList[u][i]].color == WHITE ){

            if(!cycleExists) cycleExists = DFS_visit(adjList[u][i]);

            else DFS_visit(adjList[u][i]);

        }

        else {

            cout << "Cycle detected at edge - ("<<u<<", "<<adjList[u][i]<<")"<<endl;

            cycleExists = true;
        }

    }

    vertices[u].color=BLACK;

    t++;

    vertices[u].finish= t;

    return cycleExists;

}

void DFS(){

    for(int i=0;i<num_of_verts;i++){

        vertices[i].color=WHITE;

        vertices[i].parent=NULL;

    }

    t=0;

    for(int i=0;i<num_of_verts;i++){

        if(vertices[i].color==WHITE){

           cout << "Traversing component "<<i<<"-"<<endl;


            bool cycle = DFS_visit(i);

            cycle==1? cout<<"Cycle Exists\n\n":cout <<"Cycle does not exist\n\n";

        
}
   
 }


}


int main(){


    adjList[0] = {4, -1};

    adjList[1] = {0, 5, -1};

    adjList[2] = {1, 5, -1};

    adjList[3] = {6, 7, -1};

    adjList[4] = {1, -1};

    adjList[5] = {-1};

    adjList[6] = {2, 5, -1};

    adjList[7] = {3, 6, -1};



    DFS();

    return 0;
}

Please do not recommend using `#include ` in Stack Overflow answers. [See here](https://stackoverflow.com/q/31816095/10871073). — Adrian Mole, May 17 '21 at 10:16

Back edges in a graph

5 Answers5

Here is the code for a better understand:

Linked