6. (5 Points) The object of the Kevin Bacon Game is to link a movie actor to Kev

Question

6. (5 Points) 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. Nicole Kidman has a Bacon number of 2, because she was in Cold Mountain with Donald Sutherland, who was in Animal House with Kevin Bacon. Assume that you have a comprehensive list of actors, with roles, and explain how to find an actor's Bacon number. Patrick A11en Dial M for Murder Grace Kelly Caligola Glenn Close The Stepford Wives To Catch a Thief High Noon John Gielgud Portrait of a Lady The Eagle Has Landed Lloyd Bridges Nicole Kidman Murder on the Orient Express Cold untain Donald Sutherland Kathleern Quinlan Joe Versus he Volcan An American Haunting John Belushi Animal House Hamlet performer vertex Apollo 1: Vernon Dobtcheff The Kevin Bacon sman Tom Hanks movie vertex Bi1l Paxton Wild Things The River Jude Wild Paul Herbert The Da Vinci Code Meryl Streep Enigma Serretta Wilson Kate Winslet Yves Aubert itanic Shane Zaza Eternal Sunshine of the Spotless Mind

Explanation / Answer

Solution :-

The given Kevin Bacon game shows the links of actors to Kevin Bacon via a shared role. Each movie actor has aBacon number that is the minimum number of links to link with Kevin Bacon. If we need to find the Bacon number of alll actors then we need to find the minimum number of links from the actor to Kevin Bacon. The link is represented by a movie name.

Now consider the actors name as nodes and movie names as edges then we can find the Bacon number of all actors by finding the shortest path between actor node and Kevin Bacon node. We take the Kevin Bacon node as the source vertex and every other node as a destination. As we know that it is an unweighted graph then we can use BFS( Breadth first seach) algorithm to find the shortest path between Kevin Bacon node to every other vertex.

Now the BFS algorithm can be used here to find the shortest path between Kevin Bacon to every other actor. In this algorithm prepare two queues one for visited nodes and other for unvisited nodes.

In the above given table the shortest path given of every nide from the Kevin Bacon node that is the required Bacon number. This table is produced by the BFS algorithm on the given graph. So to find the Bacon number of all the actors the BFS can be used.

Vertex Shortest path Previous vertex Kevin Bacon 0 Patrick Allen 2 Donald sutherland Grace Kelly 3 Lloyd bridges Glenn close 3 Nicole kidman John gielgud 3 Nicole kidman Nicole kidman 2 Donald sutherland Lloyd bridges 2 Tom hanks Donald sutherland 1 Kevin Bacon Kathleen quinlan 1 Kevin Bacon John belushi 1 Kevin Bacon Vernon dobtcheff 2 Donald sutherland Bill paxton 1 Kevin Bacon Tom hanks 1 Kevin Bacon Meryl streep 1 Kevin Bacon Paul herbert 2 Bill paxton Kate winslet 2 Bill paxton Yves aubert 2 Tom hanks Shane zaza 2 Tom hanks Serretta wilson 2 Tom hanks

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.