Visited Set

A visited set records which states or vertices have already been discovered or processed.

It prevents repeated work and protects graph traversal from cycles.

Core Idea

When an algorithm reaches a vertex, it checks whether that vertex has already been seen. If it has, the algorithm skips it. If not, the algorithm records it and continues.

The exact moment of marking matters. In BFS, marking when a vertex is enqueued often avoids duplicate queue entries.

Python Example

visited = set()
 
if node not in visited:
    visited.add(node)
    # process node

The set makes membership checks fast in typical cases.

Common Confusions

Visited does not always mean “fully processed.” Some algorithms need separate states such as unvisited, visiting, and done.

The key stored in visited must represent the full state. In a grid problem with keys or remaining fuel, (row, col) alone may not be enough.

When To Use It

Use a visited set in BFS, DFS, graph traversal, state-space search, and any algorithm where the same state can be reached more than once.