Assign each data structure to at least one scenario: Explain: 1. why you chose t
ID: 3576458 • Letter: A
Question
Assign each data structure to at least one scenario: Explain:
1. why you chose the data structure.
2. whether you would use java's implementation of the data structure.
3. describe why the data structure is the best for efficiency.
Scenerio 5: Six degrees of Kevin Bacon is a game where you link actors to Kevin Bacon. It is based on the scientific finding that in order for a person to contact anyone in the world it would take at most 6 links from one person to another. In the game, actors are linked to Kevin Bacon based on movies that they are in. So if someone is in a movie with Kevin Bacon, then they are 1 degree away. If they are in a movie with someone who is in a movie with Kevin Bacon, then they are 2 degrees away, and so on. What type of data structure should be used to keep track of this kind of connectivity?
Explanation / Answer
A graph is most appropriate for this structure, with Kevin Bacon at the root node. By measuring the depth of a node, the degrees of separation from Kevin Bacon can be calculated very easily. Java's implementation for this cannot be used, as it does not have a method to directly calculate the depth. This method must be implemented by the programmer. Since a graph structure is efficient like a binary search, the data structure is appropriate for efficiency. A graph also promotes relationships between grandchildren and root, which is not possible in a tree, and a graph is thus representative of the real life situation.