20.4.3. Reconstructing Paths in BFS

Try these first

1. 1.

   What is the main purpose of the BFS algorithm?

   Hint

   Think about how BFS discovers vertices.

2. 2.

   Define the term 'parent vertex' in the context of BFS.

   Hint

   Consider how we keep track of where we came from in BFS.

3. 3.

   What does BFS stand for?

   • Breadth First Search
   • Best First Search
   • Breadth Final Search

   Hint

   Recall the name of the algorithm.

4. 4.

   T/F: BFS can find the shortest path in terms of number of edges.

   • True
   • False

   Hint

   Think about how BFS explores the graph.

5. 5.

   Given a directed graph, implement the BFS algorithm and provide the pseudocode, explaining why each step is necessary in the context of pathfinding.

   Hint

   Think about the main objectives of each BFS strategy.

6. 6.

   Describe how you would adjust the BFS algorithm to handle weighted graphs where the shortest path is defined not just by the number of edges but by edge weight. Suggest an algorithm for this.

   Hint

   Consider how BFS could misidentify paths if weights are involved.