Java Reference
In-Depth Information
works regardless of whether the graph is directed or undirected. To ensure visiting
all vertices,
graphTraverse
could be called as follows on a graph G:
voidgraphTraverse(GraphG){
intv;
for(v=0;v<G.n();v++)
G.setMark(v,UNVISITED);//Initialize
for(v=0;v<G.n();v++)
if(G.getMark(v)==UNVISITED)
doTraverse(G,v);
}
Function “
doTraverse
” might be implemented by using one of the graph traver-
sals described in this section.
11.3.1 Depth-First Search
The first method of organized graph traversal is called depth-first search (DFS).
Whenever a vertex V is visited during the search, DFS will recursively visit all
of V's unvisited neighbors. Equivalently, DFS will add all edges leading out of v
to a stack. The next vertex to be visited is determined by popping the stack and
following that edge. The effect is to follow one branch through the graph to its
conclusion, then it will back up and follow another branch, and so on. The DFS
process can be used to define a depth-first search tree. This tree is composed of
the edges that were followed to any new (unvisited) vertex during the traversal, and
leaves out the edges that lead to already visited vertices. DFS can be applied to
directed or undirected graphs. Here is an implementation for the DFS algorithm:
/
**
Depthfirstsearch
*
/
staticvoidDFS(GraphG,intv){
PreVisit(G,v); //Takeappropriateaction
G.setMark(v,VISITED);
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(G.getMark(w)==UNVISITED)
DFS(G,w);
PostVisit(G,v); //Takeappropriateaction
}
This implementation contains calls to functions
PreVisit
and
PostVisit
.
These functions specify what activity should take place during the search. Just
as a preorder tree traversal requires action before the subtrees are visited, some
graph traversals require that a vertex be processed before ones further along in the
DFS. Alternatively, some applications require activity after the remaining vertices
are processed; hence the call to function
PostVisit
. This would be a natural
opportunity to make use of the visitor design pattern described in Section 1.3.2.
Figure 11.8 shows a graph and its corresponding depth-first search tree. Fig-
ure 11.9 illustrates the DFS process for the graph of Figure 11.8(a).
