20.1. Breadth First Search (BFS)

Try these first

1. 1.

   What data structure does BFS primarily use for managing vertices?

   Hint

   Think about the order in which nodes are processed.

2. 2.

   Define what an adjacency matrix is.

   Hint

   Consider how connections between nodes would be represented.

3. 3.

   What is the time complexity of BFS in terms of n and m?

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

   Hint

   Recall how BFS processes the graph based on its structure.

4. 4.

   True or False: BFS can find the shortest path in a weighted graph.

   • True
   • False

   Hint

   Think about what BFS does differently from other algorithms.

5. 5.

   Design a BFS algorithm that not only finds the shortest path from vertex A to vertex B but also outputs a list of all vertices visited in order.

   Hint

   Incorporate both the parent array for path reconstruction and the visit list in your BFS implementation.

6. 6.

   How would you modify BFS to handle a situation where the graph changes dynamically? For example, edges can be added or removed during execution.

   Hint

   Think about the impact of edge modifications on the traversal.