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

Question

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?

Answer 1

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.

And the following picture is of a 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

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.