Practice question · Sort into groups
Sort each task by which traversal is the natural fit.
Groups: Use BFS · Use DFS
- Topologically sort tasks with dependencies
- Find the nearest reachable vertex by edge count
- Find the shortest route in an unweighted maze
- Detect a cycle in a dependency graph
Hints
- Shortest-by-edges and nearest-first are BFS strengths.
- Cycle detection and topological sort come naturally from DFS.
Show the answer
Use BFS: Find the shortest route in an unweighted maze, Find the nearest reachable vertex by edge count
Use DFS: Detect a cycle in a dependency graph, Topologically sort tasks with dependencies
Why
BFS suits shortest-edge and nearest-first questions; DFS suits cycle detection and topological sorting. Matching the traversal's exploration order to the task is the whole skill.
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…
- Select every true statement about graph traversal.