Graph Traversal

Before you learn BFS/DFS, make sure these are solid:

1) Graph representations (you already know this)

• •Adjacency list: for each vertex u, store list of neighbors N(u). Great when the graph is sparse.
• •Adjacency matrix: an n×n table where entry (u,v) indicates if an edge exists. Great for dense graphs or O(1) edge queries.

2) Queue/Stack basics (quick refresh)

• •Queue (FIFO): first in, first out. Operations: enqueue, dequeue.
• •Stack (LIFO): last in, first out. Operations: push, pop.

3) What “unweighted shortest path” means

• •In an unweighted graph, every edge counts as cost 1.
• •The “shortest path” from s to v is the path with the fewest edges.
• •BFS (not DFS) gives shortest-path distances in this sense.

4) Edge cases you must handle (important for correctness)

• •Self-loop (u → u): If you mark visited[u] when discovered, then when you later scan neighbors and see u again, you ignore it. No infinite loop.
• •Parallel edges (multiple edges u → v): You may see v repeated in adjacency lists. visited[v] prevents adding v to the frontier multiple times.
• •Disconnected graph: Starting from s only reaches its connected component (or reachable set in directed graphs). To traverse the entire graph, you run traversal from every unvisited vertex.
• •Directed vs undirected: In directed graphs, reachability follows edge direction.

One key theme across everything you’re about to do: traversal is not “visit each vertex once by magic.” It’s a careful combination of:

• •a frontier that stores discovered vertices you still need to process
• •a policy for which frontier element to extract next (FIFO vs LIFO)
• •a visited[v] marker to guarantee termination and keep work bounded

A graph traversal is a procedure that explores all vertices reachable from a given start vertex s, in a systematic order.

Why do we need a traversal at all?

In a tree, you can “just” walk children pointers and never worry about coming back around. In a general graph, you can have:

• •cycles (A → B → C → A)
• •multiple ways to reach the same vertex (A → D and A → B → D)

Without a rule to avoid revisiting, you can loop forever.

The three atomic concepts

1) Reachability

Given a graph G = (V, E) and start vertex s, traversal explores:

• •All v ∈ V such that there exists a path from s to v.

If there is no path from s to v, traversal from s will never visit v.

2) Frontier / extraction policy

Traversal maintains a frontier: vertices that have been discovered but not fully processed.

• •If you extract vertices in FIFO order, you get Breadth-First Search (BFS).
• •If you extract vertices in LIFO order, you get Depth-First Search (DFS).

This single design choice drastically changes the order of exploration and the properties you can prove.

3) Visited marking

We maintain a boolean marker:

• •visited[v] = true means “v has been discovered already.”

This prevents:

• •infinite loops (cycles)
• •repeated work (multiple edges pointing to same vertex)

A subtle but crucial detail is when you set visited[v]. The standard and safest approach is:

• •Mark visited[v] when you discover v (i.e., when you push/enqueue it into the frontier), not when you pop/dequeue it.

If you delay marking until extraction, then parallel edges (or converging paths) can insert the same vertex many times, bloating runtime.

Traversal skeleton (shared idea)

Here’s the shared structure both BFS and DFS follow:

1) Initialize all visited[v] = false

2) Create an empty frontier

3) Add s to frontier, set visited[s] = true

4) While frontier not empty:

• •remove a vertex u according to some policy
• •for each neighbor v of u:
• •if not visited[v]: set visited[v] = true and add v to frontier

The only difference is the frontier policy (queue vs stack).

Why BFS exists (motivation)

Suppose you’re in a social network graph and want to find people closest to you:

• •distance 1: direct friends
• •distance 2: friends-of-friends
• •distance 3: three hops away

You want to explore in “layers” of increasing hop count. That is exactly what BFS does.

Key idea: FIFO creates layers

BFS uses a queue, so vertices discovered earlier are processed earlier.

That enforces a level-by-level expansion from the start vertex s.

We often track a distance array (optional but common):

• •dist[v] = number of edges in the shortest path from s to v (in an unweighted graph)

Initialize:

• •dist[s] = 0
• •when you discover v from u, set dist[v] = dist[u] + 1

BFS pseudocode (adjacency list)

Assume the graph is stored as adjacency lists Adj[u].

BFS(G, s):
  for each vertex v in V:
    visited[v] = false
    dist[v] = +∞
    parent[v] = NIL

  visited[s] = true
  dist[s] = 0
  Q = empty queue
  enqueue(Q, s)

  while Q not empty:
    u = dequeue(Q)
    for each v in Adj[u]:
      if visited[v] == false:
        visited[v] = true
        dist[v] = dist[u] + 1
        parent[v] = u
        enqueue(Q, v)

What BFS guarantees (and why)

Claim (unweighted shortest paths): When BFS first discovers a vertex v, dist[v] is the length (in edges) of the shortest path from s to v.

Intuition:

• •The queue ensures all vertices at distance 0 are processed, then all at distance 1, then distance 2, etc.
• •So the first time you reach v, it must be via the smallest possible number of edges.

A useful view is “BFS tree”:

• •parent[v] pointers form a tree (or forest) of shortest paths from s.

Complexity

Let n = |V| and m = |E|.

• •With adjacency lists: BFS runs in O(n + m).
• •Each vertex is enqueued at most once.
• •Each edge is scanned at most once (directed) or twice (undirected).
• •With adjacency matrix: scanning neighbors costs O(n) per vertex, so O(n²).

Edge cases revisited under BFS

• •Self-loop u→u: when scanning neighbors of u, you see u but visited[u] is already true.
• •Parallel edges u→v repeated: the first time you see v you enqueue it; subsequent times visited[v] blocks duplicates.
• •Directed graphs: BFS respects direction; reachability and distances apply along directed paths.

Why DFS exists (motivation)

Sometimes you don’t care about shortest hop count. You care about structure:

• •Is there a path from s to some target t? (DFS can find one quickly in practice)
• •Does the graph have cycles?
• •Can we order tasks with dependencies? (topological sort uses DFS)
• •What are strongly connected components? (DFS is a key ingredient)

DFS explores “as deep as possible” before backtracking.

Two equivalent implementations

1) Recursive DFS (uses the call stack implicitly)

2) Iterative DFS (uses an explicit stack)

They behave similarly, but iterative DFS avoids recursion depth limits.

Recursive DFS pseudocode

DFS(G, s):
  for each vertex v in V:
    visited[v] = false
    parent[v] = NIL

  dfsVisit(s)

  dfsVisit(u):
    visited[u] = true
    for each v in Adj[u]:
      if visited[v] == false:
        parent[v] = u
        dfsVisit(v)

Iterative DFS (explicit stack) pseudocode

To match the “mark when discovered” rule:

DFS_iter(G, s):
  for each vertex v in V:
    visited[v] = false
    parent[v] = NIL

  S = empty stack
  visited[s] = true
  push(S, s)

  while S not empty:
    u = pop(S)
    for each v in Adj[u]:
      if visited[v] == false:
        visited[v] = true
        parent[v] = u
        push(S, v)

Note: This iterative version’s exact visitation order depends on neighbor ordering in Adj[u]. That’s normal.

What DFS guarantees (and what it doesn’t)

DFS guarantees:

• •It visits all vertices reachable from s.
• •It produces a DFS tree via parent pointers.

DFS does not guarantee shortest paths.

Example intuition:

• •DFS might go s→a→b→c… (very deep) even if there is a direct edge s→c.

Complexity

Same as BFS:

• •Adjacency list: O(n + m)
• •Adjacency matrix: O(n²)

Edge cases under DFS

Identical handling as BFS with visited marking:

• •Self-loops and parallel edges are harmless.
• •Cycles do not cause infinite recursion/loop because visited stops revisits.

A small but important note: “discovered” vs “finished”

Some DFS-based algorithms (topological sort, SCC) track timestamps:

• •discovery time (when visited becomes true)
• •finish time (when you return from recursion)

You don’t need timestamps to traverse, but it’s helpful to know DFS has a natural notion of “finishing” a node after exploring its descendants.

BFS vs DFS: how to choose

They solve different kinds of problems. The frontier policy is the whole story.

Traversal as a “subroutine”

Many bigger algorithms start with “run BFS/DFS from …”

• •Topological Sort: DFS finishing order gives a valid linear ordering in DAGs.
• •Shortest Paths: BFS is the shortest-path algorithm for unweighted graphs; Dijkstra generalizes to weighted.
• •Minimum Spanning Trees: Not the same as traversal, but MST algorithms rely on graph structure and edge scanning; being comfortable with adjacency lists and visited concepts transfers directly.
• •Strongly Connected Components: DFS explores reachability; SCCs are about mutual reachability.
• •Graph Coloring: Traversal helps you color connected components and perform checks (though optimal coloring is harder).

Traversing the entire graph (graph may be disconnected)

So far we assumed a start node s. If you want to visit every vertex in the graph:

for each vertex v in V:
  if visited[v] == false:
    BFS(G, v)   // or DFS(G, v)

This produces a forest of BFS/DFS trees—one per connected component (undirected) or per reachable region (directed).

One more practical detail: adjacency list + duplicates

Because adjacency lists can contain repeated neighbors (parallel edges), you should always structure the neighbor scan as:

• •check visited[v] before pushing/enqueueing

This keeps runtime tight: each vertex enters the frontier once.