Algorithms in a Nutshell

(^140) | Chapter 6: Graph Algorithms
Each of these adjacency representations contains the same information. Suppose,
however, you were writing a program to compute the cheapest flights between
any pair of cities in the world that are served by commercial flights. The weight of
an edge would correspond to the cost of the cheapest direct flight between that
pair of cities (assuming that airlines do not provide incentives by bundling flights).
In 2005, Airports Council International (ACI) reported a total of 1,659 airports
worldwide, resulting in a two-dimensional matrix with 2,752,281 entries. The
question “how many of these entries has a value?” is dependent upon the number
of direct flights. ACI reported 71.6 million “aircraft movements” in 2005, roughly
translating to a daily average of 196,164 flights. Even if all of these flights repre-
sented an actual direct flight between two unique airports (clearly the number of
direct flights will be much smaller), this means that the matrix is 93% empty—a
good example of a sparse matrix!
When representing an undirected graph using adjacency lists, there are opportuni-
ties to reduce the storage space. To demonstrate, assume a vertexuhas edges to
the following adjacent vertices: 2, 8, 1, 5, 3, 10, 11, and 4. First, the adjacent
vertices could be stored in increasing order to enable rapid failure when checking
whether an edge (u,v) exists. Under this scheme, checking whether edge (u,6)
exists would require only six comparisons, although eight adjacent vertices exist.
Of course, adding an edge no longer takes constant time, however, so there is a
tradeoff decision to be made. Second, to improve the performance of the check to
see whether edge (u,v) exists, the adjacency list could store the ranges of the adja-
cent vertices; this example requires eight nodes in the adjacency list, which could
be reduced to three: 1–5, 8, and 10–11. This scheme also reduces the check to
determine whether an edge exists, while slowing down the performance when
adding or removing an edge.
Graph Analysis
When applying the algorithms in this chapter, the essential factor that determines
whether to use an adjacency list or adjacency matrix is whether the graph is
sparse. We compute the performance of each algorithm in terms of the number of
vertices in the graph, |V|, and the number of edges in the graph, |E|. As is
common in the literature on algorithms, we simplify the presentation of the
formulas that represent best, average, and worst case by usingVandEwithin the
big-O notation. Thus O(V) means a computation requires a number of steps that
is directly proportional to the number of vertices in the graph. However, the
density of the edges in the graph will also be relevant. Thus O(E) for a sparse
graph is on the order of O(V), whereas for a dense graph it is closer to O(V^2 ).
As we will see, some algorithms have two different variations whose performance
changes based upon the structure of the graph; one variation might execute in
O((V+E)logV) time, while another executes in O(V^2 +E) time. Which one is
more efficient? Table 6-1 shows that the answer depends on whether the graphG
is sparse or dense. For sparse graphs, O((V+E)logV) is more efficient, whereas
for dense graphs O(V^2 +E) is more efficient. The table entry labeled “Break-even
graph” identifies the type of graphs for which the expected performance is the
same O(V^2 ) for both sparse and dense graphs; in these graphs, the number of
edges is on the order of O(V^2 /logV).
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use