Java Reference
In-Depth Information
Each edge in a directed graph has a direction from one vertex to another. The edges in an undirected graph
are bidirectional.
●
A path from one vertex to another is a sequence of edges. The length of the path is the number of these
edges. A simple path passes through each of its vertices once. A cycle is a path that begins and ends at the
same vertex. A simple cycle passes through its other vertices once.
●
The edges in a weighted graph have values called weights or costs. A path in a weighted graph has a weight,
or cost, that is the sum of its edge weights.
●
A graph that has a path between every pair of distinct vertices is connected. A complete graph has an edge
between every pair of distinct vertices.
●
Two vertices in an undirected graph are adjacent if they are joined by an edge. In a directed graph, vertex
i
is
adjacent to vertex
j
if a directed edge begins at
j
and ends at
i
. Adjacent vertices are called neighbors.
●
You can traverse the vertices in a graph by using either a depth-first traversal or a breadth-first traversal. A
depth-first traversal follows a path that goes as deeply into the graph as possible before following other
paths. A breadth-first traversal visits all neighbors of a vertex before visiting the neighbors' neighbors.
●
A directed graph without cycles imposes an order on its vertices called a topological order. This order is not
unique. You use a topological sort to discover these orders.
●
You can use a depth-first traversal of a graph to see whether a path exists between two given vertices.
●
You can modify the breadth-first traversal of a graph to find the path between two given vertices that has the
fewest edges.
●
You can modify the breadth-first traversal of a weighted graph to find the path between two given vertices
that has the lowest cost.
●
E
XERCISES
1.
Suppose that five vertices are arranged at the corners of an imaginary pentagon. Draw a connected graph that
contains these vertices.
2.
Describe each graph in Figure 28-22, using the terms introduced in Segments 28.1 through 28.4.
FIGURE 28-22
Graphs for Exercise 2
(a)
(b)
(c)
3.
Consider a graph that represents acquaintances among people. Each vertex represents a person. Each edge
represents an acquaintance between two people.
a.
Is this graph directed or undirected?
b.
Consider all vertices adjacent to a given vertex
x
. What does this set of vertices represent?
c.
What does a path in this graph represent?
d.
In what circumstance might one want to know the shortest path between two vertices in this graph?
e.
Is the graph associated with all the people alive on January 1, 1995, connected? Justify your answer.
