Learning About the Graph Construct using Games, Part III - Depth First Traversals
(Page 5 of 6 )
A traversal is like walking on the nodes of a graph. The purpose of a traversal is to visit all nodes of a graph. There are several traversal methods such as Breadth first traversal and Depth first traversal. We will concentrate on depth first traversal here, since it is simpler. Using traversals, we will be able to find paths and loops easily in the graph.
A depth first traversal tries to go as deep as possible in the graph before visiting nodes near to the starting point. For example in a graph like this:
If we start at node a, it will try to go as deep as possible, so a possible scenario could be… a->b->c->d->e->f->g->h (a depth first traversal is clearly not unique, we could have started with the path to c)
Depth first traversal is extremely easy to code. For every node, we mark it as visited and recursively call the traversal for each of the unvisited neighboring nodes. (I hope you are familiar with the concept of recursion. If not, please check my article here: http://www.devshed.com/c/a/Practices/Solving-Problems-with-Recursion/)
Here is the code for a simple depth first traversal:
void depthFirstTraversal(int u)
{
System.out.println("Visiting node "+u);
visited[u]=true;
for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
{
if(!visited[w.id])
depthFirstTraversal(w.id,v,color);
}
}
We are assuming the same adjacency list representation from parts 1 and 2. I hope you haven't already forgotten about them. Each node has a linked list holding all the nodes to which it is connected.
So, what does Depth First traversal have to do with path finding? A lot, actually! A slight modification of this function will allow us to find a path (or a loop) between two nodes in a graph.
The idea is simple. To find a path from u to v, we will keep traversing the graph starting at u till we hit the node v. Before we visit any node, we mark the edge leading to it as taken. If no path is found through this path, we reset the state of the edge to not taken. When we stop after hitting v, the path leading from u to v will be marked as taken. Pretty simple, eh?
Here is the modified function:
boolean markPath(int u,int v,int color)
{
visited[u]=true;
for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
{
if(w.color!=0)
continue;
markColor(u,w.id,color);
if(w.id==v)
return true;
if(!visited[w.id])
if(markPath(w.id,v,color))
return true;
markColor(u,w.id,0);
}
return false;
}
You may notice we have an extra parameter, called color. This is because, as we mentioned before, we are going to be finding a path, and several loops, so it is important to distinguish them. We mark the edge we take by a certain color, to indicate it belongs to a certain loop, or path.
The second observation is the markColor function. What is it? Remember in part 1 when we talked about undirected graphs, and how they are represented by two edges between any two nodes instead of one. The two edges must be treated as one. The markColor function simply colors the two versions of the edge: the one going from u to v, and the one going from v to u.
void markColor(int u,int v,int color)
{//mark the 2 versions of the edge (u,v) with color
for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
{
if(w.id==v)
{
w.color=color;
break;
}
}
for(node2 w=((node)(data.elementAt(v))).links;w!=null;w=w.next)
{
if(w.id==u)
{
w.color=color;
break;
}
}
}
Next: Solving the Problem >>
More Development Cycles Articles
More By Mohamed Saad
