Insight Vault

Visited Set

3 min read

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.

The visited set is part of the algorithm’s correctness. In a graph with cycles, traversal without visited tracking may never stop. In a graph with many paths to the same vertex, traversal without visited tracking may repeat large amounts of work.

Usage Contract

The visited key must represent the full state, not merely the most visible position.

For ordinary graph traversal, the key may be a vertex name or number. For state-space search, the key may need to be a tuple such as (row, col, keys_mask).

Python Example

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

The set makes membership checks fast in typical cases.

Full State Must Be Visited

The visited key must include every part of the state that changes future possibilities.

For a normal grid search, this may be enough:

visited.add((row, col))

For a grid with keys, it may need more:

visited.add((row, col, keys_mask))

The same position with different keys can lead to different future moves. Treating them as the same visited state can make the algorithm wrong.

Visited, Visiting, Done

Some algorithms need more than one visited state. Directed cycle detection often uses:

  • Unvisited: not seen yet.
  • Visiting: currently in the recursion path.
  • Done: fully processed.

This distinction matters because reaching a visiting node means a cycle, while reaching a done node does not.

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.

Another common mistake is sharing one visited set across separate searches when the searches are supposed to be independent. Sometimes that is correct, such as counting connected components. Sometimes each search needs its own visited state.

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.

If an algorithm revisits the same place repeatedly, or if a cycle is possible, ask what the visited key should be.

The Main Point

A visited set is correct only when its key represents the full state. Missing state information can make the algorithm skip a situation that should remain distinct.

Backlinks

Graph

Depth 1