20.4.1. Tracking Parent Vertices

Try these first

1. 1.

   Define an adjacency matrix.

   Hint

   Think about how two vertices are related.

2. 2.

   What data structure is commonly used in BFS to keep track of vertices to be explored?

   Hint

   Remember the FIFO principle.

3. 3.

   What structure does BFS use to manage vertices to be explored?

   • Stack
   • Queue
   • Array

   Hint

   It's the opposite of the structure that explores the last added item first.

4. 4.

   True or False: BFS guarantees the shortest path in terms of the number of edges in a weighted graph.

   • True
   • False

   Hint

   Think about how edges might affect traversal.

5. 5.

   Given a graph with 10 vertices and known edges, write out the BFS execution steps starting from vertex 1, track all parents and levels.

   Hint

   Pay attention to how you fill the queue and mark levels.

6. 6.

   Explain why a graph might require adjustments when converting from adjacency matrix to adjacency list.

   Hint

   Consider how many edges exist relative to the maximum possible edges.