Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (discovered and all its neighbours was visited). What is the purpose of this distinction? It seems that DFS algorithm will never visit a visited vertex regardless of whether it's grey or black.

share|improve this question

3 Answers 3

up vote 3 down vote accepted

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to explicitly make these distinctions for better understanding.

Of course, there are actual uses of these colors. Consider a directed graph $G$. Suppose you want to check $G$ for the existence of cycles. In an undirected graph, if the node under consideration has a black or grey neighbor, it indicates a cycle (and the DFS does not visit it as you mention). However, in case of a directed graph, a black neighbor does not mean a cycle. For example, consider a graph with 3 vertices - $A, B,$ and $C$, with directed edges as $A \to B$, $B \to C$, $A \to C$. Suppose the DFS starts at $A$, then visits $B$, then $C$. When it has returned to $A$, it then checks that $C$ has already been visited and is black. But there is no cycle in the graph.

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. There could be other examples too, but you should get the idea.

share|improve this answer
    
+1 good explanation. For simple traversal of all node in an undirected graph (like one linked in my question body), do GREY and BLACK have no functional difference? –  user6805 Feb 11 '13 at 15:29
    
@user6805 For simple traversal - visiting every node - of both directed or undirected graph, there is no functional difference between grey and black. You can use only two colors (or visited/not visited). It is for more complex algorithms that you need colors. –  Paresh Feb 11 '13 at 16:55

It is an exercise in CLRS that you can remove the gray or black color and the algorithm works fine with just two colors, in other words it is not really needed. The main goal of marking vertices is to make sure we don't run into an infinite loop by repeatedly visiting already visited vertices.

The reason for using 3 colors in DFS algorithm is mainly pedagogical: it is conceptually clearer, it helps students see what is going on during the execution for each node.

share|improve this answer

Grey vertex states that you have visited that node and moved on to one of its neighbors in some order, but there might be more neighboring vertices to that node. It while be useful while backtracking for exploring unvisited vertices.

Let's say Vertex A has two neighbors B and C and B has one neighbor D.

start at vertex A which is white color and make it grey and traverse to its neighbor.

Lets say by choosing alphabetical order it visits vertex B which is in white color and marks as grey.

Then visits D of white -> grey D -> no more neighbors. hence marks D->black.

Now, backtracks to B in Grey and no more nieghbors. Hence marks B-> black.

AGain backtracks A in grey and visits c mark to c->Grey no more neighbors marks C as black

finally, back to A and marks vertex A as black as there are no more white vertices and all as black.

share|improve this answer
    
I don't see if the distinction between grey and black has any purpose here.. –  user6805 Feb 11 '13 at 15:30
    
that's what you have to understood. If a vertex is marked as black, it means there wouldn't be any neighboring vertices to that vertex. Here vertex D marked to black as there are no neighbor vertices.. where as grey suggests there are more neighbors to visit and hence you traverse through those. –  NRK Feb 11 '13 at 18:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.