Know this before you start: “A visited set so you never loop forever”
The visited set
Graphs can loop back on themselves. Remember every node you've reached in a set and never process one twice, or you'll go round forever.
The idea
Unlike trees, graphs can have cycles: 1 → 2 → 3 → 1. A search that doesn't remember where it's been revisits nodes endlessly.
Keep a set of visited nodes. Add a node when you first discover it (for BFS: when you put it in the queue), and skip any neighbour that's already in the set. Each node is then handled exactly once.
For grids you can mark cells in place (change '1' to '0') instead of using a set.
See it step by step
Cycle 1 → 2 → 3 → 1, start at 1
- Visit 1, mark it. Its neighbour 2: new → visit, mark.
- 2's neighbour 3: new → visit, mark. 3's neighbour 1: already marked → skip.
- Done after 3 visits instead of looping forever.
In code (Python)
def reachable(graph, start):
seen = {start}
stack = [start]
while stack:
node = stack.pop()
for nxt in graph[node]:
if nxt not in seen: # never twice
seen.add(nxt)
stack.append(nxt)
return seen
cycle = {1: [2], 2: [3], 3: [1]}
print(sorted(reachable(cycle, 1))) # [1, 2, 3]O(V) extra space; keeps the search at O(V + E).
When you'll use it
- Every graph traversal and every grid search.
Common mistakes
- Marking too late (after popping) so the same node is queued many times.
- Sharing one visited set across searches that should be independent.
