CODEWITHSUNDEEP
algorithmgraphgraph-theorydepth-first-searchtarjans-algorithm
Vlad Iordache
Vlad Iordache

Reputation: 528

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

Upvotes: 12

Views: 27963

Answers (5)

Proma Progga
Proma Progga

Reputation: 22

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;
}

Upvotes: -2

Sandipan Dey
Sandipan Dey

Reputation: 23101

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

Upvotes: 6

Lajos Arpad
Lajos Arpad

Reputation: 76464

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.

Upvotes: 4

gue
gue

Reputation: 2018

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

Upvotes: 18

DAle
DAle

Reputation: 9117

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.

Upvotes: 1

Related Questions