liveBook · Manning

Visited set

As explained in Algorithms Every Programmer Should Know

A visited set is a collection of graph vertices already encountered during traversal.

A visited set is a checklist of graph vertices a traversal has already encountered. Graphs can contain cycles, so without this check a traversal may follow connections back to earlier vertices and loop forever. section 1.4.5

During traversal, the set helps control which vertices get processed:

  • In depth-first search (DFS), check whether a vertex has been visited; if it has, backtrack instead of following it again. section 1.4.5
  • In breadth-first search (BFS), track visited vertices as the queue expands outward, preventing the layers from cycling back indefinitely. section 1.4.5

A Python DFS

An iterative DFS starts with an empty set. When it pops a node from its stack, it processes the node only if it is not already in the set, then adds it before considering its neighbors. section 1.4.5

Figure 1.11 Traversal paths shown through a network with a cycle. Left: Depth-First Search (DFS) traces deep pathways until it detects dead-ends and mismatches. Right: A Breadth-First Search (BFS) expands to all neigboring or adjacent nodes. Both traversals use a visited set to track already visited nodes to avoid infinite loops.

Compare DFS and BFS paths through a cyclic graph; both use a visited set to avoid infinite loops. section 1.4.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the check-and-record role and demonstrates it in iterative DFS code, without showing a BFS implementation.
Examples
Uses a cyclic graph traversal and a Python DFS implementation with a set and stack.
What you can do after
Apply it by tracking encountered vertices so graph traversals stop revisiting them.
How it connects
Connects graph traversal to depth-first search, breadth-first search, queues, and stacks.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.