20.5. Shortest Path in Unweighted Graphs

Try these first

1. 1.

   What does BFS stand for?

   Hint

   Think of how the algorithm explores a graph.

2. 2.

   In which context would you use an adjacency list rather than an adjacency matrix?

   Hint

   Consider storage efficiency.

3. 3.

   What does BFS stand for?

   • Breadth First Search
   • Best Fast Search
   • Binary First Search

   Hint

   Think about the search method used.

4. 4.

   True or False: BFS can be used for weighted graphs to find the shortest path.

   • True
   • False

   Hint

   Recall the conditions for BFS applicability.

5. 5.

   Given an undirected graph represented as an adjacency list, implement BFS to find all reachable nodes from a starting node and return them in a list.

   Hint

   Utilize a queue for managing nodes to visit next.

6. 6.

   Describe how to modify BFS to also track the distance from the source vertex to each node.

   Hint

   Think about how BFS layers relate to the coefficient of distance.