20.4.2. Tracking Levels

Try these first

1. 1.

   What is the purpose of the BFS algorithm?

   Hint

   Think about how we visit neighbors in a sequential order.

2. 2.

   What data structure is used to manage vertices in BFS?

   Hint

   Remember the order of processing vertices.

3. 3.

   What does BFS stand for?

   • Best-First Search
   • Breadth-First Search
   • Binary First Search

   Hint

   Think about the meaning of breadth in exploring a graph.

4. 4.

   True or False: BFS can only be used on unweighted graphs.

   • True
   • False

   Hint

   Consider if BFS ensures the shortest path in all scenarios.

5. 5.

   Given a graph representation of a social network, construct a BFS traversal starting from a specified user and list all the connections made. Then reconstruct the path back to the originating user for a selected connection.

   Hint

   Ensure you note how many levels deep each connection goes and use parents to trace the full path.

6. 6.

   Create a graph representing a course prerequisite structure and demonstrate how BFS can be used to find if a specific course can be reached given a set of enrolled courses. Then indicate the path taken from any enrolled course to that target course.

   Hint

   Think of enrolled courses as multiple starting points and track the paths with parent pointers.