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
