Practice question · Select all that apply
Select every true statement about graph traversal.
Hints
- One option swaps the data structures of the two traversals.
- DFS uses a stack, not a queue.
Show the answer
- A. A traversal without a visited set can loop forever on a cyclic graph
- B. BFS finds the fewest-edge path from the start in an unweighted graph
- C. Dijkstra's algorithm needs a priority queue
- E. BFS and DFS both run in O(V + E)
Why
Both traversals are O(V + E); BFS gives shortest unweighted paths; Dijkstra uses a priority queue; and the visited set prevents infinite loops. 'DFS uses a queue' is false. DFS uses a stack.
Practise Graph Algorithms and Traversal
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Graph Algorithms and Traversal
- Order the steps of breadth-first search from a start vertex.
- Swapping the queue in breadth-first search for a stack turns it into depth-first search, changing what the…
- A graph traversal on a graph with cycles runs forever without a visited set. Why does the set fix it, and…
- Sort each task by which traversal is the natural fit.