20.3. BFS Algorithm

Try these first

1. 1.

   What does BFS stand for?

   Hint

   Remember the order of exploration!

2. 2.

   How is a graph represented using an adjacency list?

   Hint

   Consider which representation is more efficient for sparse graphs.

3. 3.

   What is the purpose of BFS in graph theory?

   • To find the shortest path
   • To discover the graph structure
   • To visit all vertices

   Hint

   Think about the graph traversal method.

4. 4.

   True or False: BFS can find paths in weighted graphs.

   • True
   • False

   Hint

   Recall how BFS measures distance.

5. 5.

   In a graph with 8 vertices and 7 edges, illustrate the BFS traversal starting from vertex 1. What will the queue look like after visiting each vertex?

   Hint

   Remember to keep track of visited vertices.

6. 6.

   Given an unweighted graph, how does BFS compare to Dijkstra’s algorithm in terms of finding paths?

   Hint

   Think of scenarios where weights alter the shortest path.