Java Reference
In-Depth Information
/
**
Recursivetopologicalsort
*
/
staticvoidtopsort(GraphG){
for(inti=0;i<G.n();i++)//InitializeMarkarray
G.setMark(i,UNVISITED);
for(inti=0;i<G.n();i++)//Processallvertices
if(G.getMark(i)==UNVISITED)
tophelp(G,i); //Recursivehelperfunction
}
/
**
Topsorthelperfunction
*
/
staticvoidtophelp(GraphG,intv){
G.setMark(v,VISITED);
for(intw=G.first(v);w<G.n();w=G.next(v,w))
if(G.getMark(w)==UNVISITED)
tophelp(G,w);
printout(v); //PostVisitforVertexv
}
Figure11.13
Implementation for the recursive topological sort.
J6
J1
J2
J5
J7
J3
J4
Figure11.14
An example graph for topological sort. Seven tasks have depen-
dencies as shown by the directed graph.
We can implement topological sort using a queue instead of recursion, as fol-
lows. First visit all edges, counting the number of edges that lead to each vertex
(i.e., count the number of prerequisites for each vertex). All vertices with no pre-
requisites are placed on the queue. We then begin processing the queue. When
Vertex V is taken off of the queue, it is printed, and all neighbors of V (that is, all
vertices that have V as a prerequisite) have their counts decremented by one. Place
on the queue any neighbor whose count becomes zero. If the queue becomes empty
without printing all of the vertices, then the graph contains a cycle (i.e., there is no
possible ordering for the tasks that does not violate some prerequisite). The printed
order for the vertices of the graph in Figure 11.14 using the queue version of topo-
logical sort is J1, J2, J3, J6, J4, J5, J7. Figure 11.15 shows an implementation for
the algorithm.
11.4
Shortest-Paths Problems
On a road map, a road connecting two towns is typically labeled with its distance.
We can model a road network as a directed graph whose edges are labeled with
