Depth-First Search in Graphs - Putting it together
(Page 3 of 4 )
The DFS search should be called first on the root item, and further on with all of the non-visited vertexes, in this way assuring that the entire tree will be traveled. This happens when you have a graph that is not connected, like a forest (two individual trees, for example). Here is the code snippet that makes all this happen in our program; we just need to extend the DFS a little:
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])
{
ancient[p->value] = vertex;
distance[p->value] = distance[vertex] +1;
p->type = TREE_EDGE;
DFS(p -> value);
}
else
{
if( color[p->value] == GRAY)
{
p->type = BACK_EDGE;
}
else
if (distance[p->value] > distance[vertex])
{
p->type = AHEAD_EDGE ;
}
else
p->type = CROSS_EDGE ;
}
color[vertex] = BLACK;
}
Here is a picture of a graph during the DFS. The search just arrived at node 11. The edges that will form the tree are marked with a solid line; the edges that are back-pointing are dashed lines; the cross edges are marked with dotted lines; and finally, the ahead-pointing edges show a dash-and-dot line.
-->Image Courtesy of Kátai Zoltán- Introduction to Graphs<--
1 -> 2 3 4
2 -> 5
3 -> 6
4 ->
5 -> 7 8
6 -> 9 10
7 ->
8 -> 1 2
9 -> 11
10 -> 3
11 -> 3 12 13 14
12 -> 8 15 20
13 -> 16
14 -> 17 18
15 -> 19 20
16 -> 21 22
17 ->
18 -> 9
19 -> 12
20 -> 11
21 ->
22 -> 13
1 2 5 7 8 3 6 9 11 12 15 19 20 13 16 21 22 14 17 18 10 4
Tree edges: 1 - 2 1 - 3 1 - 4 2 - 5 3 - 6 5 - 7 5 - 8 6 - 9 6 - 10 9 - 11 11 - 12 11 - 13 11 - 14 12 - 15 13 - 16
14 - 17 14 - 18 15 - 19 15 - 20 16 - 21 16 - 22
Back Pointing edges: 8 - 1 8 - 2 10 - 3 11 - 3 18 - 9 19 - 12 20 - 11 22 - 13
Edges pointing ahead: 12 - 20
Cross edges: 12 - 8
Next: The topological order >>
More Code Examples Articles
More By Gabor Bernat
/ 5 
