What Is a Visited Set? Stopping a Graph Search from Looping
A visited set remembers vertices a search has already queued. Without it, a cycle in an undirected graph makes the walk repeat forever.
A visited set is the memory a graph search keeps so it does not walk the same vertex twice. A tree does not need one for a child walk, because the only way back to a node is up the call stack. A graph can contain a cycle.
How it works
Build an adjacency list so each vertex can name its neighbours. Start from the source and mark it when you enqueue it, not when you dequeue it. Marking later lets the same neighbour sit in the queue once for every edge that finds it.
The size of the component is the number of marks, including the start. A start vertex with no edges is a component of one. Reaching every vertex means that count equals the number of vertices you were told exist.
Breadth-first search uses the set beside a queue and answers fewest edges when every edge costs the same. Depth-first search uses the same set beside a stack or recursion and answers reachability. Neither is safe on a cyclic graph if the set is missing.
Press Run to execute this example. Use console.log to print a value.
Expected output: [0, 1, 2]. Vertex 2 is marked when vertex 0 enqueues it, so the later edge from vertex 1 cannot enqueue a duplicate.
Worked example
Start with queue [0] and mark 0. Processing 0 marks and queues 1 and 2. Processing 1 sees 0 and 2 already marked. Processing 2 sees only marked neighbours. The queue empties after exactly three vertex visits despite the cycle.
Why it is correct
Every queued vertex is reachable: the start is reachable from itself, and each newly queued neighbour extends an existing path by one edge. Conversely, when a reachable vertex is processed, every unmarked neighbour is queued, so induction on path length shows that every vertex reachable from the start is eventually discovered. Mark-on-enqueue ensures each vertex enters the queue at most once, even in a cycle.
Cost
With adjacency lists, each reached vertex is processed once and each outgoing adjacency entry is inspected once. A full traversal is O(V + E) time and O(V) extra space for marks, the queue, and the returned order. An adjacency matrix would require O(V²) inspection instead.
In the course
Graphs and breadth-first search introduce the mark-on-enqueue rule, then ask whether you can reach a vertex and what the shortest path is. The Connected components lesson asks for the component size, whether the walk reaches every vertex from 0 through count - 1, and then how many components that whole range contains, including vertices that never appear in an edge. See breadth-first search for the queue that carries the marks, and depth-first search when the question is only which vertices share a piece.
Common mistakes
Marking a vertex only when you dequeue it. The queue can then hold many copies, and a sloppy loop can look stuck.
Storing an undirected edge in only one direction. The walk reaches one end and not the other.
Forgetting to mark the start. An isolated vertex then looks like a component of zero.
When to use it
Use a visited set on any graph search, and on any walk that might return to a vertex through a different edge.
When not to
Do not use a visited set to block a tree recursion that is supposed to see both children. A child is not a repeat of the parent. The null child is the stop.
Problem-solving checklist
Decide what a vertex identifier is and use one representation consistently. Mark when scheduling work, not when finishing it. Include the start in the visited structure. Test a cycle, an isolated vertex, disconnected components, and two paths to the same neighbour.
Optional enrichment
Return all connected components of an undirected graph. Start a new search from each unvisited vertex and prove that every vertex appears in exactly one returned component.