Graph traversal and the visited set

Walking a graph looks like walking a tree — go to a node, then visit its neighbours — with one crucial addition: graphs can have cycles. If a → b and b → a, a naive traversal bounces between them forever. The fix is a visited set: remember every node you've already entered, and never enter it twice.

Depth-first on a graph

function dfs(graph, node, visited):
    if visited[node]:
        return
    visited[node] = true
    // process node
    for each next in graph[node]:
        dfs(graph, next, visited)

Breadth-first on a graph

visited = { start: true }
queue = [start]
while queue is not empty:
    node = queue.removeFirst()
    // process node
    for each next in graph[node]:
        if not visited[next]:
            visited[next] = true
            queue.append(next)

The golden rule

Mark a node visited the first time you see it, not when you finish it. For BFS, mark when you enqueue (as above); otherwise the same node can be queued many times. For DFS, the if visited[node] { return } guard at the top does the job.

Cost

Each node is entered once and each edge examined once, so traversal is O(V + E) — vertices plus edges. The visited set adds O(V) space on top of the recursion or queue. With this single tool — traversal plus a visited set — you can solve reachability, connected components, shortest unweighted paths, and every grid problem in this section.