Java Reference
In-Depth Information
FIGURE 28-11
A trace of a depth-first traversal beginning at vertex A of a
directed graph
topVertex nextNeighbor Visited vertex vertexStack traversalOrder
(top to bottom)
(front to back)
A
A
A
D
A
G
A
A
B
B
BA
AB
B
BA
E
E
EBA
ABE
B
E
H
E
EBA
F
F
FEBA
ABEF
F
FEBA
C
C
CFEBA
ABEFC
C
F
I
C
FEBA
F
FEBA
H
H
HFEBA
ABEFCH
H
HFEBA
I
I
IHFEBA
ABEFCHI
I
HFEBA
H
FEBA
F
EBA
E
BA
B
A
A
A
D
D
DA
ABEFCHID
D
DA
G
GDA
ABEFCHIDG
G
DA
D
A
A
empty
ABEFCHIDG
Topological Order
28.14
Figure 28-8 shows a graph that represents the prerequisite structure of a group of computer science
courses. This graph is a directed graph without cycles. Recall that you can place the vertices of such
a graph in a topological order.
Note: In a topological order of the vertices in a directed graph without cycles, vertex a pre-
cedes vertex b whenever a directed edge exists from a to b .
The vertices in a graph can have several different topological orders. For example, one such
order for the graph in Figure 28-8 is cs1, cs2, cs5, cs4, cs7, cs9, cs10, cs6, cs8, cs3. That is, if you
complete the courses in this order, you will satisfy all prerequisites. Suppose that you can move
the vertices in the graph so that they align in this order, stretching the edges as needed. The result
will be like the graph in Figure 28-12a. Each edge points toward a node that comes after the
edge's origin node. You will be able to find at least one such arrangement for every directed
graph, if the graph has no cycles. Figure 28-12 shows two other topological orders for the graph
 
 
Search WWH ::




Custom Search