The object of the Kevin Bacon Game is to link a movie actor to Kevin Bacon via s
ID: 3027281 • Letter: T
Question
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 Forrest 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 comprehensive list of actors, with roles, and do the following:
a) 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.
Explanation / Answer
a. Build a graph with a vertex corresponding to each actor such that there is an edge between two actors if and only if they were in the same movie. To find an actors Bacon number is simply a matter of finding the shortest path betweenthe vertex corresponding to the actor and the vertex corresponding to Kevin Bacon in this graph.
b. Find the shortest path between the vertex corresponding to Kevin Bacon and every other vertex. The vertex with the longest “shortest path” to it corresponds to the actor with the highest Kevin Bacon number.
c. Find the shortest path between them