15
$\begingroup$

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.

$\endgroup$
24
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ +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? $\endgroup$ – user6805 Feb 11 '13 at 15:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Paresh Feb 11 '13 at 16:55
  • $\begingroup$ I understood it! OK, consider the following case: twitter.com/MaksimADmitriev/status/796995958043279361 We traverse the graphs using DFS. The graph on the left is the same as the graph from this answer, and it doesn't have cycles. Let's traverse the graph on the right which has a cycle. We visit A and mark it grey. We visit B and mark it grey. We visit C and mark it grey. Now we 're about to visit A which is already grey. So "from black to black" doesn't mean there is a cycle, but "from grey to grey" does. That's why we need grey. Please correct me if I'm wrong $\endgroup$ – Maksim Dmitriev Nov 11 '16 at 8:50
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't see if the distinction between grey and black has any purpose here.. $\endgroup$ – user6805 Feb 11 '13 at 15:30
  • $\begingroup$ 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. $\endgroup$ – NRK Feb 11 '13 at 18:01
  • $\begingroup$ I believe it saves you from simply re-visiting nodes you know for certain have no back edges (i.e. optimization) $\endgroup$ – Setheron Aug 26 '14 at 17:50
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OK but what's the point? You've said that white/gray/black is related to forward/back/cross/tree but you don't say what those things are for, either. So now there are seven things the asker doesn't understand, instead of just three! $\endgroup$ – David Richerby Mar 21 '18 at 21:07
  • $\begingroup$ These edges can be used in various application of DFS, like back edges are used in identifying loops in a graph, Forward and cross edges are used to Test if unique path exists between every pair of vertices. $\endgroup$ – Neeraj Singh Apr 11 '18 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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