Graphs - Data Structures and Abstractions with Java - page 739

graph has no cycles. We mark the vertex as visited and push it onto a stack. We continue by finding
another vertex u that is unvisited and whose neighbors, if any, are visited. We mark u as visited and
push it onto the stack. We proceed in this way until we have visited all the vertices. At that time, the
stack contains the vertices in topological order, beginning at the top of the stack.
The following algorithm describes this topological sort:

Algorithm getTopologicalOrder()
vertexStack = a new stack to hold vertices as they are visited
numberOfVertices = number of vertices in the graph
for (counter = 1 to numberOfVertices)
{

nextVertex = an unvisited vertex whose neighbors, if any, are all visited
Mark nextVertex as visited
vertexStack.push(nextVertex)

}
return vertexStack

Figure 28-14 traces this algorithm for the graph in Figure 28-8. At each iteration of the
algorithm's loop, nextVertex becomes shaded in the figure as it is visited. The topological order is
the opposite of the order in which this shading occurs. In this example, the topological order is the
one pictured in Figure 28-12a.

FIGURE 28-14

Finding a topological order for the graph in Figure 28-8

(a)

cs3 cs6 cs8

(b)

cs3 cs6 cs8

cs1 cs2 cs4

cs7 cs9 cs10

cs1 cs2 cs4 cs7 cs9 cs10

cs5

cs5

(c) (d)

cs3 cs6 cs8

cs3 cs6 cs8

cs1 cs2 cs4 cs7 cs9 cs10

cs1 cs2 cs4 cs7 cs9 cs10

cs5

cs5

(e) (f)

cs3 cs8

cs3 cs6 cs8 cs6

cs1 cs2 cs4 cs7 cs9 cs10 cs1 cs2 cs4 cs7 cs9 cs10

cs5 cs5

(continues on the next page)