Depth-First Search in Graphs - The code snippet and classification
(Page 2 of 4 )
This method reminds us of recursive iteration throughout the graph. As opposed to the BFS, the DFS is harder to comprehend, but easier to write. Again, for the best performance, the right way to store the graph inside of memory is with the adjacency list. The search can be wrapped up in just the following few lines:
void DFS(int vertex)
{
printf(" %d " , vertex);
pListIt p;
color[vertex] = GRAY; // visited
for (p = adjacencyList[vertex]; p != NULL; p = p -> p_next)
if (!color[p -> value])
{
DFS(p -> value);
}
color[vertex] = BLACK;
}
For those of you who skipped my article about the breadth first search, I need to explain that to better simulate the state of the vertex I made a definition that a vertex is white if it has not yet been visited, gray if it is currently being visited, and black if it has been visited. Therefore, all we need to do is call the search for a vertex; if we find a neighbor that has not yet been visited, call the DFS for that vertex also. Let the recursion handle the rest.
You may observe that the items are visited in the FIFO (First in First Out) order that is simulated by a stack. Yet we do not need to write the stack data structure ourselves, as the recursion will also implement this feature. This is why it is a little simpler to write a DFS than a BFS, where we need to manually simulate the queue. Nevertheless, you may write a non-recursive DFS (implemented with loops) where you need to use the stack also.
The order in which we drop by the vertexes will build the DFS search of the graph. As for the categorization of the edges, first we should know what kind of edges exist, so let us look at a little citation from my article about the BFS:
"A tree edge means that the edge will become a part of the search tree (we traveled ahead on it inside the graph or found another vertex through it). Back-pointing edges are the ones that will point to a node already black (it points to an earlier generation vertex). Cross-pointing edges are gray, and their distance from the root is less than the distance from the root of the currently visited node."
The DFS puts each edge in one of these four categories when it first observes its existence during the search. As we visit only to the edges that we have not yet visited (remember, visited edges are black), it is logical that our search will build a tree. This has all the edges through which we found another vertex. Additionally, we can classify the other edges as I explain in the next paragraph.
Let us be at a vertex u. Moreover, we visit all of its neighbors, which we mark here with letter v. If v is white, the edge is a tree edge; if it is gray, it will be a back-pointing edge. If it is black, there are two cases. We measure the distance of the vertexes from the root, and if the distance of vertex v is larger than of vertex u we have an ahead-pointing edge, otherwise it will be a cross-pointing edge.
Next: Putting it together >>
More Code Examples Articles
More By Gabor Bernat
/ 5 
