Graphs and paths - Data Structures and Problem Solving Using Java - page 569

number of courses. Given a list of courses and their prerequisites, com-
pute a schedule that requires the minimum number of semesters.

The object of the Kevin Bacon Game is to link a movie actor to Kevin
Bacon via shared movie roles. The minimum number of links is an
actor's Bacon number . For instance, Tom Hanks has a Bacon number
of 1. He was in Apollo 13 with Kevin Bacon. Sally Field has a Bacon
number of 2 because she was in Forest Gump with Tom Hanks, who
was in Apollo 13 with Kevin Bacon. Almost all well-known actors
have a Bacon number of 1 or 2. Assume that you have a comprehen-
sive list of actors, with roles, and do the following.
a.

14.26

Explain how to find an actor's Bacon number.

b. Explain how to find the actor with the highest Bacon number.

c. Explain how to find the minimum number of links between two

arbitrary actors.

The input is a two-dimensional maze with walls, and the problem is
to traverse the maze, using the shortest route, from the upper left-
hand corner to the lower right-hand corner. You may knock down
walls, but each wall you knock down incurs a penalty p (that is speci-
fied as part of the input).

14.27

Suppose you have a graph in which each vertex represents a computer
and each edge represents a direct connection between two computers.
Each edge ( v , w ) has a weight p v , w representing the probability that a
network transfer between v and w succeeds (0 < ). Write a
program that finds the most reliable way to transfer data from a desig-
nated starting computer s to all other computers in the network.

14.28

p vw ≤ 1

,

references

The use of adjacency lists to represent graphs was first advocated in [3]. Dijk-
stra's shortest-path algorithm was originally described in [2]. The algorithm
for negative edge costs is taken from [1]. A more efficient test for termination
is described in [6], which also shows how data structures play an important
role in a wide range of graph theory algorithms. The topological sorting algo-
rithm is from [4]. Many real-life applications of graph algorithms are pre-
sented in [5], along with references for further reading.

R. E. Bellman, “On a Routing Problem,” Quarterly of Applied Mathemat-
ics 16 (1958), 87-90.

1.

E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,”
Numerische Mathematik 1 (1959), 269-271.

2.