MediumPython ProgrammingHigh School (11–12)High School (9–10)UndergraduateGeneralPython Going Further › Data StructuresConceptualPython-Coded
In the friends graph below, find by breadth-first search, on paper, the shortest path from Kabir to…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
In the friends graph below, find by breadth-first search, on paper, the shortest path from Kabir to Ana, and write the queue and the previous dictionary after each step.
The friends. Asha knows Ravi and Kabir. Ravi knows Asha, Meera and Kabir. Meera knows Ravi and Ana. Kabir knows Asha and Ravi. Ana knows Meera. The search looks at each person's friends in this order.
The worked solution
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, compare your working with the solution.
Plan. The friends are: Asha knows Ravi and Kabir. Ravi knows Asha, Meera and Kabir. Meera knows Ravi and Ana. Kabir knows Asha and Ravi.
Start: queue [Kabir], previous {Kabir: None}.
- Take Kabir. Neighbours Asha and Ravi are new. Previous: Asha from Kabir, Ravi from Kabir. Queue
[Asha, Ravi]. - Take Asha. Neighbours Ravi (seen) and Kabir (seen). Nothing new. Queue
[Ravi]. - Take Ravi. Neighbours Asha (seen), Meera (new), Kabir (seen). Previous: Meera from Ravi. Queue
[Meera]. - Take Meera. Neighbours Ravi (seen) and Ana (new). Previous: Ana from Meera. Queue
[Ana]. - Take Ana: this is the goal. Walk back: Ana from Meera, Meera from Ravi, Ravi from Kabir.
The path, reversed: Kabir, Ravi, Meera, Ana: 3 steps.
Answer: ['Kabir', 'Ravi', 'Meera', 'Ana'].
Discussion (0)
Log in to join the discussion.
Loading…