CODEWITHSUNDEEP
algorithmdata-structuresgraph
Hemant Bhargava
Hemant Bhargava

Reputation: 3585

Detecting a cycle in a graph (Using three color mechanism)

I know how to detect a cycle in a graph using the three colors (Black, White and Gray) mechanism. For those who do not know this, please follow this : http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Briefly, White nodes are nodes which are undiscovered, Gray is for the nodes which are under processing and Black nodes are the ones which are discovered.

A couple of days back, one senior guy asked me why one needs exactly three colors for this purpose. Why can't we do it only with Black and White? Why are Gray nodes really needed? My bad that I could answer this question to him. Can anyone of you tell if he was asking me a valid question or just testing me?

Upvotes: 4

Views: 4954

Answers (5)

curiousengineer
curiousengineer

Reputation: 2627

Two colors for directed graph are also enough. Assuming the convention for white grey and black to be what we have been reading, the only reason to have black color is an optimization. If we eliminate grey, we will end up revisiting a node that is still not processed fully and fail to detect a cycle, but if we do not maintain a black node list, it will only cause the algorithm to traverse nodes and the neighbors more than once or maybe even many times, but it will still work fine as long as white and grey nodes are used the same way

Upvotes: 0

Satyam Gupta
Satyam Gupta

Reputation: 11

For an undirected graph, 2 colours will suffice. But for the directed graph we'll need 3 colours. The reason, why we need 3 colours for the directed graph is clear from this example: when we have visited node D and all its neighbours then it becomes black. When we reach this node again from some previous node A using another path, we realise this node is already been visited, also since its colour is black it means at that node we have explored all the neighbours and there was no path to node A from D and we have backtracked. So we conclude there that there is no cycle between A and D.

Consider another case in directed graph, if we have used only two colours when we reach D from A second time using another path, we get node D as a grey colour which means it has been visited in the first round so we conclude that the cycle exists which is actually not the case. That's the importance of 3rd colour.

Upvotes: 1

Prem KTiw
Prem KTiw

Reputation: 605

No, he wasn't testing you. You can detect cycles in a graph using just two colors, but the graph must be undirected in that case.

Elaboration

What I want to emphasize is that graphs are of two kinds on the basis of the way edges are directed, when we have a graph when we have al the edges going forward as well as backward between two vertices, the type of graph is called undirected graph.

The Picture you see is of an undirected graph

And the following picture is of a directed graph.

The Directed Graph

The way these two differ on paper is that we don't draw direction of edge in undirected graph, whenever we say there exists an edge between node A and B in context of an undirected graph, it automatically follows that the reverse edge also exists.Why we even talk of reverse edge, the reason being in computer programs the way edges are represented in different representations, we indicate directed edges only, for example in an adjacency list Node B will be in adjacency list of A only if there is an edge from A to B, and so in this representation, if we need to show that there exists an edge from B to A as well then we also need to add Node A in the adjacency list of B.

Similarly in case of adjacency matrix based representaion the matrix is symmetric about it's leading diagonal(the diagonal which starts from left top), to show that for every edge that exists from A to B , there also exists an edge from B to A.

So to realize any undirected graph we do following

Replacing edges

So after you replace all the edges of an undirected graph by this, you see the actual picture of the graph in computer's representation.

Now assume that you have been given a graph. You must ask, which one ?

An undirected Graph

I will talk in reference to First Picture posted here. And assume that the adjacency list representation has been used to represent the graph.

How will that look like? Here you see:

A : B -> D -> E -> NULL
B : A -> D -> E -> NULL
C : D -> NULL
D : A -> B -> C -> NULL
E : A -> B -> NULL

The objective is to devise some strategy to check if a cycle exists or not.

Now suppose that these nodes represents some shops in a city and the edges are roads, so if you see a road from node A to B then automatically there exists a road from B to A, as the graph is undirected. The same is evident from the adjacency list as well.

To detect a cycle in undirected graph, we will follow the following procedure in a way, a typical program will follow. And then you will see how the statement I gave is valid. So let's start.

We start from Node A, in mood to traverse the whole graph, traversal here means you want to visit all the shops. Now to really keep track of which all shops you have visited you color them, as you leave them, so you are standing at node A and now you have got many roads emerging from node A, which you can take to go somewhere else. All these options are present in the adjacency list for A.

Let's say you choose a road to Node B, and you follow it , leaving A , and before leaving A you color it. Now standing at B you first see , is that node colored ? you see no !! and then you know that you have not visited this node before. Again want to do same thing, so you see for the adjacency list of B to choose next road, you see a road to A, you again follow that path and reach A, Color B as you leave. But as soon as you reach node A you see it's being colored, it means you have visited this shop before, but then you realize that because the graph is undirected therefore reaching at A from B is not an issue, as the edges are bidirectional, and so you backtrack.

To avoid this again you use a parent array, where par[i] = j, if you discovered i from j. Now you have eliminated the pitfall of visiting parent again. now you choose next road from B, which is to E, you go there, color B, and this time set par[E] = B, when you reach E, you want to do same thing again. But this time you see a road to A, first you check is A your parent ? because you don't want to visit your parent again as you came from there itself.

Which is NO here. so you go to A, but as soon as you reach A, you notice that the node is colored. And if this is true then it means you have already visited A, and that means there exists a path from A which ends at A again, hence a cycle.

So tell me how many colors we used? Only two, one is initial color and the other one after visiting the node.

You may say I have showed it on this specific example and so procedure may not work always, but try realizing the situation i described with the feel of traversal, and try convincing yourself that if you start from a node and following a set of roads if you reach somewhere and see that the node is colored, it means you have already visited that node, and because you are avoiding visiting the node's parent therefore the only way you can see a node colored is because of some cycle.

I am leaving it to you to realize that why this thing do not works in a directed graph, and where is the mechanics of bidirectional edge is coming here.

Upvotes: 6

Shubham Jindal
Shubham Jindal

Reputation: 21

#include<bits/stdc++.h>
using namespace std;
list<int>adj[10000];
int flag =0;
void dfs(int s , bool visited[] , char color[]){
    visited[s] = true;
    color[s] = 'g';
    std::list<int>::iterator ii;
    for(ii=adj[s].begin() ; ii!=adj[s].end(); ii++){
        if(visited[*ii]==false){
            visited[*ii]=true;
            color[*ii]='g';
            dfs(*ii , visited , color);
        }
        else if(visited[*ii]==true && color[*ii]=='g'){
            flag=1;
        }
    }
    color[s] = 'b';
}
int main(){
    int n,m,x,y,i;
    cin>>n>>m;
    for(i=0; i<m; i++){
        cin>>x>>y;
        adj[x].push_back(y);
    }
    bool visited[n+1];
    char color[n+1];
    for(i=0; i<n; i++){
        visited[i] = false;
        color[i] = 'w';
    }
    dfs(0 , visited , color);
    if(flag==1)
    {
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

Upvotes: 0

Coderslang Master
Coderslang Master

Reputation: 368

Here is all you the explanation you need

https://cs.stackexchange.com/questions/9676/the-purpose-of-grey-node-in-graph-depth-first-search

Basically, white nodes turn grey after you visit them for the first time but grey nodes become black only after all their neighbours turned black, or they don't have any unvisited neighbours.

In a directed graph, a cycle is present if and only if a node is seen again before all its descendants have been visited. In other words, if a node has a neighbor which is grey, then there is a cycle (and not when the neighbor is black). A grey node means we are currently exploring its descendants - and if one such descendant has an edge to this grey node, then there is a cycle. So, for cycle detection in directed graphs, you need to have 3 colors.

Now it should be pretty clear that two colors won't suffice.

Upvotes: 4

Related Questions