Practice question · Multiple choice
A graph traversal on a graph with cycles runs forever without a visited set. Why does the set fix it, and what does it cost?
Hints
- Follow a cycle by hand without marking anything. Where do you end up?
- Ask how much memory a visited set needs relative to the graph.
Show the answer
A. Because a cycle returns you to a node you already expanded
Why
Without marking, a cycle is an infinite loop; with it, every node is expanded once and the traversal is O(V+E). The memory is O(V) and unavoidable, which becomes the binding constraint on enormous graphs, where bloom filters and external-memory algorithms replace the exact set.
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.