Graphs - Data Structures and Abstractions with Java - page 731

begins at j and ends at i . In Figure 28-5, vertex A is adjacent to vertex B , but vertex B is not adjacent
to vertex A . That is, vertex A is vertex B 's neighbor, but the converse is not true.
When convenient, we will place vertex labels within the circles that represent the vertices, as in
Figure 28-5. But sometimes, the vertex labels will appear next to the circles, as in Figure 28-3.

FIGURE 28-5

Ve r t e x A is adjacent to vertex B , but B is not adjacent to A

B

A

28.6

The number of edges. If a directed graph has n vertices, how many edges can it have? If the graph
is complete, each vertex is a neighbor of all the other vertices. Thus, each vertex ends n - 1 directed
edges. Consequently, the graph has n ( n - 1) edges. A complete undirected graph has half that num-
ber of edges. For example, the graph in Figure 28-4b has 4 vertices and 4 × 3 / 2, or 6, edges. To

make the graph directed and complete, we would replace each edge with two directed edges, which
results in a graph having 12 edges.

Note: If a graph has n vertices, it can have at most

n ( n - 1) edges if the graph is directed

●

n ( n - 1) / 2 edges if the graph is undirected

●

A graph is sparse if it has relatively few edges. It is dense if it has many edges. While these
terms have no precise definition, we will say that a sparse graph has O( n ) edges, and a dense graph
has O( n 2 ) edges. The graph in Figure 28-1 has eight vertices and eight edges. It is sparse.

Note: Typical graphs are sparse.

Airline Routes
28.7

A graph that represents the routes that an airline flies is similar to one that represents a road map.
They are different, however, because not every city has an airport, and not every airline flies to or
from every airport. For example, the graph in Figure 28-6 shows the flights for a small airline on
the East Coast of the United States. The graph is undirected and consists of two subgraphs that are
each connected. The entire graph, however, is disconnected.
Notice that you can fly from Boston to Provincetown, but not from Boston to Key West.
Algorithms exist that see whether a flight between given cities is possible.

Note: Figure 28-6 contains one graph that consists of two distinct subgraphs. Although
each subgraph is connected, the entire graph is disconnected.