Java Reference
In-Depth Information
A
B
A
B
C
C
D
D
F
F
E
E
(A)
(B)
Figure11.8
(a) A graph.
(b) The depth-first search tree for the graph when
starting at Vertex A.
DFS processes each edge once in a directed graph. In an undirected graph,
DFS processes each edge from both directions. Each vertex must be visited, but
only once, so the total cost is (jVj + jEj).
11.3.2
Breadth-First Search
Our second graph traversal algorithm is known as a breadth-first search (BFS).
BFS examines all vertices connected to the start vertex before visiting vertices fur-
ther away. BFS is implemented similarly to DFS, except that a queue replaces
the recursion stack. Note that if the graph is a tree and the start vertex is at the
root, BFS is equivalent to visiting vertices level by level from top to bottom. Fig-
ure 11.10 provides an implementation for the BFS algorithm. Figure 11.11 shows
a graph and the corresponding breadth-first search tree. Figure 11.12 illustrates the
BFS process for the graph of Figure 11.11(a).
11.3.3
Topological Sort
Assume that we need to schedule a series of tasks, such as classes or construction
jobs, where we cannot start one task until after its prerequisites are completed. We
wish to organize the tasks into a linear order that allows us to complete them one
at a time without violating any prerequisites. We can model the problem using a
DAG. The graph is directed because one task is a prerequisite of another — the
vertices have a directed relationship. It is acyclic because a cycle would indicate
a conflicting series of prerequisites that could not be completed without violating
at least one prerequisite. The process of laying out the vertices of a DAG in a
linear order to meet the prerequisite rules is called a topological sort. Figure 11.14
