20.5.1. Shortest Path Properties

Try these first

1. 1.

   Define what a graph is.

   Hint

   Think about what makes up a graph.

2. 2.

   What does BFS stand for?

   Hint

   Think about how the algorithm explores the graph.

3. 3.

   What is the function of the queue in BFS?

   • To store visited vertices
   • To manage vertices to explore next
   • To calculate distances

   Hint

   Think about the order of exploration.

4. 4.

   True or False: BFS can only be used in weighted graphs.

   • True
   • False

   Hint

   Consider the properties of BFS.

5. 5.

   Given a graph with weights, can you apply the BFS algorithm to find the shortest path? What modifications would you have to make?

   Hint

   Consider what BFS generally assumes about edge distances.

6. 6.

   If we add another component to the graph that is disconnected from the initial source, how would BFS react? What would be the result?

   Hint

   Think about how BFS operates on connected vertices.