20.3.4. Example of BFS Execution

Try these first

1. 1.

   What does BFS stand for?

   Hint

   Think about how the search explores the graph.

2. 2.

   How do we keep track of vertices that have been visited in BFS?

   Hint

   Consider whether we need to revisit vertices.

3. 3.

   What is the main advantage of using a queue in BFS?

   • To store vertices in a last-in
   • first-out manner
   • To manage which vertices to explore next in a first-in
   • first-out manner
   • To ignore vertices that have been visited

   Hint

   Think about how BFS needs to manage the order of exploration.

4. 4.

   The time complexity of BFS using an adjacency matrix is?

   • O(n)
   • O(n^2)
   • O(n + m)

   Hint

   Consider how many entries are in the matrix for n vertices.

5. 5.

   Given the following graph composed of vertices and edges, write a BFS algorithm that starts with vertex 1 and outputs the order of vertices visited.

   Hint

   Consider how neighbors are added to the queue.

6. 6.

   Design a graph with 10 vertices and at least 8 edges such that BFS starting from vertex 1 visits vertices in the order of 1, 2, 3, 4, 5, .... Write what this order reveals about the graph's structure.

   Hint

   Visualize how each vertex connects and ensures every next vertex is reached during exploration.