DSA Roadmap/Graphs

Graph Representation & Traversal (BFS/DFS)

Pick the right representation, reach for BFS or DFS on reflex, and know the Tarjan bridge check for critical edges — the foundation every other graph algorithm on this roadmap builds on.

!!!2/5Theory: 2h 10m9 problems

Why this is the hinge of the whole roadmap

Every data structure you've studied so far is secretly a graph with extra constraints: a linked list is a graph where every node has out-degree 1, a tree is a graph with no cycles and exactly one path between any two nodes, and a grid is a graph where nodes are cells and edges connect 4 (or 8) neighbors. Once you can see a problem as "vertices and edges," the traversal techniques you already trust from Trees — DFS, BFS, recursion with a visited set — apply almost unchanged. The new work in this topic is entirely about handling what trees don't have: cycles, multiple paths to the same node, and disconnected components.

Representation: adjacency list vs. adjacency matrix

You have two default choices, and picking the right one is itself a signal interviewers watch for.

Adjacency ListAdjacency Matrix
SpaceO(V + E)O(V²)
"Are u, v connected?"O(degree(u))O(1)
Iterate all neighbors of uO(degree(u)) — optimalO(V) — wasteful
Iterate all edgesO(V + E)O(V²)
Best forSparse graphs (E ≪ V²) — the overwhelming majority of interview graphsDense graphs (E ≈ V²), or when you need O(1) edge-weight lookups
Common representationdict[node] -> list[(neighbor, weight)]grid[i][j] = weight (or 0/∞ for "no edge")

Default to an adjacency list unless the problem explicitly hands you a dense matrix (like a grid, or an "is city i connected to city j" matrix) or you need O(1) weight lookups between arbitrary pairs — Floyd-Warshall, later in this topic, is built entirely on the matrix representation for exactly that reason.

A third representation worth naming: an edge list — just a flat list of (u, v, weight) tuples. It's the natural input format for graph problems and is exactly what Kruskal's algorithm (Minimum Spanning Tree) wants, since it needs to sort edges globally rather than walk neighbor lists.

# Adjacency list from an edge list — the workhorse representation. from collections import defaultdict def build_adjacency_list(n, edges, directed=False): graph = defaultdict(list) for u, v in edges: graph[u].append(v) if not directed: graph[v].append(u) return graph

BFS vs. DFS: how to choose without hesitating

Both run in O(V + E) time and O(V) space, and both visit every reachable vertex exactly once — but they explore in a different order, and that order is the entire reason to pick one over the other.

Signal in the problemUseWhy
"Shortest path" / "minimum steps" / "fewest moves" in an unweighted graphBFSBFS explores in increasing distance from the source — the first time you reach a node is guaranteed to be via a shortest path
"Does a path exist" / connectivity / count componentsEitherOrder doesn't matter, only reachability
Cycle detectionDFSNatural via recursion-stack coloring (see Topological Sort for the directed case)
Exhaustive exploration / backtracking-style search (all paths, not just shortest)DFSMatches the call-stack-as-path-so-far model from the Backtracking topic
Level-order structure matters (e.g., "process level by level")BFSThe queue naturally batches nodes by distance
Very deep or very wide graphs where stack overflow is a riskBFS (iterative)DFS recursion depth is O(V) in the worst case (a long chain); BFS's queue doesn't have this failure mode

The rule of thumb worth saying out loud in an interview: BFS finds the shortest path in an unweighted graph because it's the only traversal that discovers nodes in strictly non-decreasing distance order. DFS gives you a path, with no such guarantee — it might hand you the longest possible route before finding the destination.

from collections import deque def bfs_shortest_path_length(graph, start, target): visited = {start} queue = deque([(start, 0)]) while queue: node, dist = queue.popleft() if node == target: return dist for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist + 1)) return -1 # unreachable

DFS: recursive vs. iterative

Recursive DFS is what you'll reach for by default — it's shorter and mirrors how you already think about tree recursion:

def dfs_recursive(graph, node, visited): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited)

The catch is the same one from Big-O & Complexity Analysis: recursion depth is O(V) in the worst case (a graph shaped like a long chain), which risks a stack overflow on large inputs — a real concern in Python, where the default recursion limit is ~1000. If an interviewer asks "can you avoid the call stack?", swap to an explicit stack:

def dfs_iterative(graph, start): visited = {start} stack = [start] order = [] while stack: node = stack.pop() order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor) return order

Note the iterative version's visitation order isn't identical to the recursive one (it depends on push order), but both are valid DFS traversals — if you need the exact recursive order, push neighbors in reverse.

Visited-set management: the #1 source of bugs

Every graph traversal needs to answer "have I already processed this node?" — get this wrong and you either infinite-loop on a cycle or redo exponential work. Two patterns, both correct, with a subtle but important difference:

  • Mark visited when you enqueue/push it (not when you pop it). In BFS especially, this is required: if you mark on pop, the same node can be enqueued multiple times by different neighbors before it's ever processed, wasting work and — in weighted or counting variants — silently breaking correctness.
  • Mark visited before recursing, at the top of the DFS call, so a node can't be re-entered while its own recursion is still in progress (which is also how you'll detect cycles later).
# BUG: marking visited on dequeue lets the same node be queued many times. # for neighbor in graph[node]: # queue.append(neighbor) # visited.add(neighbor) # should happen at enqueue time, guarded by a check # CORRECT: for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)

Multi-source BFS

A pattern that shows up constantly and surprises people who've only seen single-source BFS: instead of starting from one node, seed the queue with all starting nodes simultaneously, each at distance 0. The BFS then expands outward from all of them in lockstep, and the first time it reaches any given cell tells you the distance to the nearest source — exactly what you want for problems like "how long until every rotten orange spreads to every fresh one" or "distance from each cell to the nearest wall."

def multi_source_bfs(grid, sources): rows, cols = len(grid), len(grid[0]) dist = [[-1] * cols for _ in range(rows)] queue = deque() for r, c in sources: dist[r][c] = 0 queue.append((r, c)) while queue: r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) return dist

This is strictly better than running single-source BFS from each source separately and taking the minimum (which costs O(k · (V + E)) for k sources) — multi-source BFS does the same job in one O(V + E) pass, because every cell is still visited exactly once.

The grid-as-graph framing

A huge fraction of graph interview questions never say the word "graph" — they show you a 2D grid instead. Recognize it immediately: cells are vertices, and 4-directional (or 8-directional) adjacency is the edge set. Everything above — BFS for shortest path, DFS for connected regions, multi-source BFS for spreading processes, a visited set (or in-place mutation) to avoid revisiting — applies without modification.

def traverse_grid(grid): rows, cols = len(grid), len(grid[0]) visited = set() directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] def dfs(r, c): if (r, c) in visited or not (0 <= r < rows and 0 <= c < cols): return visited.add((r, c)) for dr, dc in directions: dfs(r + dr, c + dc) for i in range(rows): for j in range(cols): if (i, j) not in visited: dfs(i, j) # one call per connected region

Complexity, precisely

For both BFS and DFS, with an adjacency list: O(V + E) time, because every vertex is enqueued/pushed once and every edge is examined at most twice (once from each endpoint, in an undirected graph). With an adjacency matrix, it degrades to O(V²), because finding a node's neighbors means scanning an entire row regardless of how sparse it actually is — another reason to default to adjacency lists. Space is O(V) for the visited set plus the queue/stack/recursion stack.

Bridges (critical connections) — Tarjan's low-link DFS

A bridge in an undirected graph is an edge whose removal increases the number of connected components — a single point of failure in a network. Interview framing: "critical connections," "edges you must keep," "roads whose closure disconnects cities."

The standard linear-time algorithm is a DFS that timestamps discovery and tracks how far "up" a subtree can reach via back edges:

  • disc[u] — discovery time of u (assigned when DFS first enters u).
  • low[u] — the smallest discovery time reachable from u's subtree, including via one back edge.
  • Edge (u, v) (where v is a child of u in the DFS tree) is a bridge iff low[v] > disc[u] — the subtree under v has no back edge that climbs to u or above, so cutting (u, v) isolates that subtree.
def critical_connections(n, connections): graph = [[] for _ in range(n)] for u, v in connections: graph[u].append(v) graph[v].append(u) disc = [-1] * n low = [0] * n time = 0 bridges = [] def dfs(u, parent): nonlocal time disc[u] = low[u] = time time += 1 for v in graph[u]: if v == parent: continue if disc[v] == -1: dfs(v, u) low[u] = min(low[u], low[v]) if low[v] > disc[u]: bridges.append([u, v]) else: low[u] = min(low[u], disc[v]) # back edge for i in range(n): if disc[i] == -1: dfs(i, -1) return bridges

Articulation points (cut vertices) use the same disc/low arrays with a slightly different check (low[v] >= disc[u] for non-root nodes, plus a root-with-two-children rule). Know that they exist and share this DFS; bridges are the more common LeetCode ask. Strongly connected components (Kosaraju / Tarjan on directed graphs) are a related family — worth an extra-reading pass, rarely a from-scratch Senior coding ask.

Time O(V + E), space O(V + E). Do not reach for this when Union-Find suffices (incremental connectivity / cycle-forming edge); bridges answer a static "which edges are load-bearing?" question after the full undirected graph is known.

Pitfalls and interview gotchas

  • Disconnected graphs. A single BFS/DFS call from one node only reaches its connected component. If the problem asks about the whole graph (count components, visit every node), you need an outer loop over all vertices that starts a new traversal from every still-unvisited one — exactly like the grid traversal above.
  • Self-loops and multi-edges. An edge (u, u) or duplicate edges (u, v) appearing twice don't break correctness if your visited-set check is solid, but they can silently blow up naive edge-counting logic (e.g., in-degree computations for Topological Sort). Clarify with the interviewer whether the input is guaranteed simple.
  • 0-indexed vs. 1-indexed nodes. LeetCode graph problems inconsistently use both (courses are 0-indexed, but some edges inputs are 1-indexed like Redundant Connection). Always check the constraints before sizing your adjacency list/visited array — an off-by-one here is a silent wrong-answer, not a crash.
  • Revisiting nodes without a visited set → infinite loop. This is the single most common bug: on any graph with a cycle, forgetting to check "have I seen this node" turns a terminating traversal into an infinite one. Unlike a tree, you cannot assume "no way back to an ancestor."
  • Directed vs. undirected confusion. Always clarify. Adding an edge in both directions when the graph is actually directed silently turns a DAG into a cyclic graph and will break Topological Sort; forgetting to add the reverse edge on an undirected graph will make parts of it unreachable.
  • Recursion depth on adversarial inputs. A DFS on a graph shaped like a single long chain (or an unbalanced tree) recurses to depth O(V). If V can be large (10⁴+), prefer the iterative version to avoid a stack overflow that has nothing to do with your algorithm being wrong.
  • Bridge DFS: forgetting to skip the parent. On undirected graphs, the edge back to the parent is not a back edge — treating it as one makes low too small and you miss every bridge.

What's next

The remaining subtopics are all traversal plus one more idea: State-space / Implicit Graph BFS invents vertices when the problem never hands you a graph; Topological Sort is DFS/BFS plus dependency ordering; Union-Find tracks connectivity as edges are added; Shortest Paths generalizes BFS to weighted edges via a heap (see Heap Fundamentals & Top-K Pattern — Dijkstra and Prim's both lean on them). Minimum Spanning Tree lives in Advanced Niche Algorithms.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.