20.4. Path Reconstruction in BFS

Try these first

1. 1.

   What is BFS primarily used for in graph theory?

   Hint

   Think about exploring the connections among entities.

2. 2.

   Name one data structure used in BFS.

   Hint

   What follows the FIFO principle?

3. 3.

   What is the primary purpose of BFS in a graph?

   • To optimize search algorithms
   • To discover all reachable vertices
   • To find minimum spanning trees
   • To sort the graph

   Hint

   What do you achieve by searching level by level?

4. 4.

   Does BFS use recursion?

   • True
   • False

   Hint

   Consider the data structure used in BFS.

5. 5.

   Given a tree structure, implement BFS to determine if a specific target value exists. Keep track of parent nodes for path reconstruction.

   Hint

   Make sure to update your parent array while exploring.

6. 6.

   Explore a dense graph using BFS. Compare the time taken with an adjacency matrix vs. an adjacency list. Report findings.

   Hint

   Count how many edges and vertices exist to justify your observations.