Graph Theory37 sections · 1633 units
Open in Course

Quiz: Multi-Source BFS

Knowledge check

Check Your Understanding

In the Rotting Oranges problem, you push all rotten oranges into the queue before starting BFS. What would go wrong if you ran a separate BFS from each rotten orange instead?

  1. A.The answer would be wrong because BFS cannot run multiple times
  2. B.Nothing. Both approaches give the same result with the same speed
  3. C.Separate BFS runs would miss some fresh oranges
  4. D.Separate BFS runs give the correct answer but take O(kV)O(k \cdot V) time instead of O(V)O(V), where kk is the number of sources
Start the roadmap to answer the quizzes and solve the challenges