The purpose of grey node in graph depth-first search

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

In DFS we classify edges as forward-edge, back-edge , cross-edge and tree-edge.

We use 3 colors to classify the edges. and these colors represents the state of the vertex i.e v. white : the vertex v is not yet discovered.

gray : v has already been discovered , but all the vertices that are reachable from v are not yet discovered. so the vertex v is still in the stack.

black: v is already pop out of stack.discovered and finished.

In doing the DFS if you encounter a gray vertex through edge e then it's a back edge. If you encounter a black vertex through edge e then it's a cross edge/forward edge. if you encounter white vertex then you will call DFS recursively.