Java Reference
In-Depth Information
/
**
Breadthfirst(queue-based)search
*
/
staticvoidBFS(GraphG,intstart){
Queue<Integer>Q=newAQueue<Integer>(G.n());
Q.enqueue(start);
G.setMark(start,VISITED);
while(Q.length()>0){ //ProcesseachvertexonQ
intv=Q.dequeue();
PreVisit(G,v); //Takeappropriateaction
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(G.getMark(w)==UNVISITED){//PutneighborsonQ
G.setMark(w,VISITED);
Q.enqueue(w);
}
PostVisit(G,v); //Takeappropriateaction
}
}
Figure11.10
Implementation for the breadth-first graph traversal algorithm
A
B
A
B
C
C
D
D
F
F
E
E
(A)
(B)
Figure11.11
(a) A graph. (b) The breadth-first search tree for the graph when
starting at Vertex A.
illustrates the problem. An acceptable topological sort for this example is J1, J2,
J3, J4, J5, J6, J7.
A topological sort may be found by performing a DFS on the graph. When a
vertex is visited, no action is taken (i.e., function
PreVisit
does nothing). When
the recursion pops back to that vertex, function
PostVisit
prints the vertex. This
yields a topological sort in reverse order. It does not matter where the sort starts, as
long as all vertices are visited in the end. Figure 11.13 shows an implementation
for the DFS-based algorithm.
Using this algorithm starting at J1 and visiting adjacent neighbors in alphabetic
order, vertices of the graph in Figure 11.14 are printed out in the order J7, J5, J4,
J6, J2, J3, J1. Reversing this yields the topological sort J1, J3, J2, J6, J4, J5, J7.
