Java Reference
In-Depth Information
To answer this question, we first create a directed graph to represent the courses and their pre-
requisites. Figure 28-8 is an example of such a graph. Each vertex represents a course, and each
directed edge begins at a course that is a prerequisite to another. Notice, for example, that you must
complete cs1, cs2, cs4, cs7, cs9,
and
cs5 before you can take cs10.
This graph has no cycles. In a directed graph without cycles, we can arrange the vertices so that
vertex
a
precedes vertex
b
whenever a directed edge exists from
a
to
b
. The order of the vertices in
this arrangement is called a
topological order
. Later in this chapter, you will see how to find this
order and, therefore, the order in which you should complete your course requirements.
FIGURE 28-8
The prerequisite structure for a selection of courses as a
directed graph without cycles
cs3
cs6
cs8
cs1
cs2
cs4
cs7
cs9
cs10
cs5
28.10
The ADT tree is a kind of graph that uses parent-child relationships to organize its nodes in a hier-
archical fashion. One particular node, the root, is the ancestor of all other nodes in the tree. But not
all graphs have a hierarchical organization, and so not all graphs are trees.
Note:
All trees are graphs, but not all graphs are trees. A tree is a connected graph
without cycles.
Question 2
What physical systems in a typical house could you represent as a graph?
Question 3
Is the graph in Figure 28-1 connected? Is it complete?
Question 4
Is the graph in Figure 28-8 a tree? Explain.
Question 5
For the graph in Figure 28-8,
a.
Is cs1 adjacent to cs2?
c.
Is cs1 adjacent to cs4?
b.
Is cs2 adjacent to cs1?
d.
Is cs4 adjacent to cs1?
28.11
As you learned in earlier chapters, you usually search a tree for a node that contains a particular
value. Graph applications, however, focus on the connections between vertices, rather than the con-
tents of vertices. These applications often are based on a traversal of the graph's vertices.
