Graph Traversal and Connected Components

Phase 5 gave you the two traversal engines — BFS (queue, layer by layer) and DFS (stack, go deep then backtrack). Everything in this lesson reuses those exact templates; the new idea is what you do with them once a graph isn’t fully connected: figure out how many separate “islands” of nodes exist, and answer questions per-island instead of assuming one big blob.

What you’ll learn

Counting connected components in an undirected graph — the single loop-plus-traversal trick behind half of all “how many groups” problems.
Why recursive DFS can crash on large or adversarial graphs, and how to rewrite it iteratively with an explicit stack.
Components on a matrix representation (Number of Provinces) versus an edge list (Number of Connected Components), and on an implicit grid graph (flood fill).
Multi-source BFS: seeding the queue with several starting cells at once to build a “distance to nearest source” map in a single pass.

Quick recap: BFS and DFS

Both traversals visit every reachable node exactly once, using a visitedvisited set to avoid repeats. BFS uses a dequedeque and processes nodes in the order they were discovered (FIFO); DFS uses a stack (or the call stack, via recursion) and always chases the most recently discovered node first (LIFO). Swap queue.popleft()queue.popleft() for stack.pop()stack.pop() and the rest of the loop is identical — see Breadth First Search and Depth First Search in Phase 5 if you need the full walkthrough.

The pattern this lesson builds on top of that: a graph doesn’t have to be one connected blob. Some nodes might be completely unreachable from others. Counting how many separate reachable groups exist is the “connected components” problem.

Connected components in an undirected graph

The recipe is always the same: loop over every node; if it hasn’t been visited yet, it must be the start of a brand-new component, so run a full traversal from it (marking everything reachable as visited) and bump a counter.

count_components.py

from collections import deque, defaultdict
 
 
def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
    components = 0
 
    for start in range(n):
        if start in visited:
            continue
        components += 1          # 'start' was never reached before -- a NEW component
        queue = deque([start])
        visited.add(start)
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
 
    return components
 
 
n = 7
edges = [(0, 1), (1, 2), (3, 4), (5, 6)]
print("connected components:", count_components(n, edges))

count_components.py

from collections import deque, defaultdict
 
 
def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
    components = 0
 
    for start in range(n):
        if start in visited:
            continue
        components += 1          # 'start' was never reached before -- a NEW component
        queue = deque([start])
        visited.add(start)
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
 
    return components
 
 
n = 7
edges = [(0, 1), (1, 2), (3, 4), (5, 6)]
print("connected components:", count_components(n, edges))

diagram A graph with three connected components mermaid

  graph LR
    subgraph "Component A"
    N0((0)) --- N1((1))
    N1 --- N2((2))
    end
    subgraph "Component B"
    N3((3)) --- N4((4))
    end
    subgraph "Component C"
    N5((5)) --- N6((6))
    end

There’s no edge connecting any of the three subgraphs above, so a traversal started at 00 can never reach 33 or 55 — that’s exactly what “separate component” means, and why the outer for start in range(n)for start in range(n) loop has to try every node instead of stopping after the first traversal.

Recursion limits: prefer iterative DFS

recursive_dfs_danger.py

import sys
 
 
def dfs_recursive(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
 
 
# A "path graph" -- 0-1-2-3-...-n-1, one long chain with no branching.
n = 5000
graph = {i: [i - 1, i + 1] for i in range(n)}
graph[0] = [1]
graph[n - 1] = [n - 2]
 
print("Python's default recursion limit:", sys.getrecursionlimit())
# Calling dfs_recursive(graph, 0, set()) here would raise RecursionError --
# the chain is 5000 nodes deep, far past the default ~1000 limit.
print("chain length:", n, "-- deeper than the default recursion limit")

recursive_dfs_danger.py

import sys
 
 
def dfs_recursive(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
 
 
# A "path graph" -- 0-1-2-3-...-n-1, one long chain with no branching.
n = 5000
graph = {i: [i - 1, i + 1] for i in range(n)}
graph[0] = [1]
graph[n - 1] = [n - 2]
 
print("Python's default recursion limit:", sys.getrecursionlimit())
# Calling dfs_recursive(graph, 0, set()) here would raise RecursionError --
# the chain is 5000 nodes deep, far past the default ~1000 limit.
print("chain length:", n, "-- deeper than the default recursion limit")

count_components_iterative_dfs.py

def count_components_dfs(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
    components = 0
 
    for start in range(n):
        if start in visited:
            continue
        components += 1
        stack = [start]
        visited.add(start)
        while stack:                      # explicit stack -- no recursion-depth risk
            node = stack.pop()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
 
    return components
 
 
n = 6
edges = [(0, 1), (1, 2), (3, 4)]   # node 5 has no edges -- its own component
print("connected components:", count_components_dfs(n, edges))

count_components_iterative_dfs.py

def count_components_dfs(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
 
    visited = set()
    components = 0
 
    for start in range(n):
        if start in visited:
            continue
        components += 1
        stack = [start]
        visited.add(start)
        while stack:                      # explicit stack -- no recursion-depth risk
            node = stack.pop()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
 
    return components
 
 
n = 6
edges = [(0, 1), (1, 2), (3, 4)]   # node 5 has no edges -- its own component
print("connected components:", count_components_dfs(n, edges))

Components on other representations

The exact same “loop + traversal + counter” idea works no matter how the graph is handed to you.

Number of Provinces hands you an adjacency matrix (is_connected[i][j] == 1is_connected[i][j] == 1 means cities ii and jj are directly connected) instead of an edge list — only the neighbor lookup changes.

number_of_provinces.py

def find_circle_num(is_connected):
    n = len(is_connected)
    visited = set()
    provinces = 0
 
    def dfs(city):
        stack = [city]
        visited.add(city)
        while stack:
            node = stack.pop()
            for neighbor in range(n):     # scan the matrix ROW for direct connections
                if is_connected[node][neighbor] == 1 and neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
 
    for city in range(n):
        if city not in visited:
            provinces += 1
            dfs(city)
 
    return provinces
 
 
is_connected = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]
print("number of provinces:", find_circle_num(is_connected))

number_of_provinces.py

def find_circle_num(is_connected):
    n = len(is_connected)
    visited = set()
    provinces = 0
 
    def dfs(city):
        stack = [city]
        visited.add(city)
        while stack:
            node = stack.pop()
            for neighbor in range(n):     # scan the matrix ROW for direct connections
                if is_connected[node][neighbor] == 1 and neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
 
    for city in range(n):
        if city not in visited:
            provinces += 1
            dfs(city)
 
    return provinces
 
 
is_connected = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]
print("number of provinces:", find_circle_num(is_connected))

Flood fill on a grid treats each cell as a node whose neighbors are its 4 grid-adjacent cells — an implicit adjacency list you never build explicitly. The classic Flood Fill LeetCode problem recolors an entire connected region starting from one pixel:

flood_fill.py

from collections import deque
 
 
def flood_fill(image, sr, sc, new_color):
    old_color = image[sr][sc]
    if old_color == new_color:
        return image           # nothing to do -- avoids an infinite requeue loop
 
    rows, cols = len(image), len(image[0])
    queue = deque([(sr, sc)])
    image[sr][sc] = new_color
 
    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 image[nr][nc] == old_color:
                image[nr][nc] = new_color   # recoloring doubles as the visited marker
                queue.append((nr, nc))
 
    return image
 
 
image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1],
]
print("flood filled:", flood_fill(image, 1, 1, 2))

flood_fill.py

from collections import deque
 
 
def flood_fill(image, sr, sc, new_color):
    old_color = image[sr][sc]
    if old_color == new_color:
        return image           # nothing to do -- avoids an infinite requeue loop
 
    rows, cols = len(image), len(image[0])
    queue = deque([(sr, sc)])
    image[sr][sc] = new_color
 
    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 image[nr][nc] == old_color:
                image[nr][nc] = new_color   # recoloring doubles as the visited marker
                queue.append((nr, nc))
 
    return image
 
 
image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1],
]
print("flood filled:", flood_fill(image, 1, 1, 2))

Multi-source BFS: distance to the nearest source

Sometimes you don’t want to explore from one starting point — you want, for every cell, the distance to whichever of several sources is closest. Seed the queue with all sources at once (each at distance 0), and BFS’s “finish one layer before starting the next” guarantee does the rest.

multi_source_distance.py

from collections import deque
 
 
def nearest_source_distance(rows, cols, sources):
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
 
    for r, c in sources:
        dist[r][c] = 0            # every source starts the frontier at distance 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
 
 
grid_rows, grid_cols = 3, 4
sources = [(0, 0), (2, 3)]   # two starting points, e.g. two exits or two fires
for row in nearest_source_distance(grid_rows, grid_cols, sources):
    print(row)

multi_source_distance.py

from collections import deque
 
 
def nearest_source_distance(rows, cols, sources):
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
 
    for r, c in sources:
        dist[r][c] = 0            # every source starts the frontier at distance 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
 
 
grid_rows, grid_cols = 3, 4
sources = [(0, 0), (2, 3)]   # two starting points, e.g. two exits or two fires
for row in nearest_source_distance(grid_rows, grid_cols, sources):
    print(row)

sketch Multi-source BFS: distance to whichever source is closer p5.js

Two starting cells seed the queue at once. Every ring lights up the tick it's reached -- the same BFS loop as before, just with two frontiers merging into one.

Complexity

Technique	Time	Space	Notes
Component counting (BFS/DFS)	$O(V + E)$	$O(V)$	One traversal per unvisited node
Iterative DFS	$O(V + E)$	$O(V)$	Same bound, but no recursion-depth risk
Flood fill on an `r x cr x c` grid	$O(r \cdot c)$	$O(r \cdot c)$	Each cell is a node with 4 implicit neighbors
Multi-source BFS	$O(r \cdot c)$	$O(r \cdot c)$	Same traversal, queue just starts with more than one node

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1971 — Find if Path Exists in Graph · Easy

Problem. Given an undirected graph with nn vertices and an edge list, determine whether a path exists from sourcesource to destinationdestination.

Constraints. 1 <= n <= 2 * 10^51 <= n <= 2 * 10^5, no duplicate edges or self-loops.

Examples. n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 gives TrueTrue · n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], 0 -> 5n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], 0 -> 5 gives FalseFalse

Editorial

The work is in the representation: an edge list is not traversable, so the first step is always building an adjacency list, adding both directions for an undirected graph.

Time $O(V + E)$ . Space $O(V + E)$ .

(1, [], 0, 0)(1, [], 0, 0) is why the source == destinationsource == destination guard exists: with no edges the traversal finds nothing, but a node trivially reaches itself.

n = 2 * 10^5n = 2 * 10^5 is the reason for the explicit stack. A recursive DFS on a path-shaped graph would need 200,000 frames and raise RecursionErrorRecursionError — one of the most common avoidable failures on large graph inputs.

Union-find also solves this, and is the better choice if you must answer many connectivity queries on a graph that keeps growing. For a single query, one traversal is simpler and equally fast.

Follow-ups: “Many queries?” — precompute components with union-find or one pass of component labelling, then each query is $O(1)$ . “Directed graph?” — add only one direction, and reachability stops being symmetric. “Shortest path rather than existence?” — BFS. “Count the components?” — loop over all nodes, traversing from each unvisited one.

LC 1466 — Reorder Routes to Make All Paths Lead to the City Zero · Medium

Problem. nn cities form a tree with n - 1n - 1 directed roads. Return the minimum number of roads that must be reversed so every city can reach city 00.

Constraints. 2 <= n <= 5 * 10^42 <= n <= 5 * 10^4, the underlying undirected graph is a tree.

Examples. n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] gives 33 · n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] gives 22

Editorial

The trick is to traverse the undirected tree while remembering the original directions. Storing each edge twice — forward with cost 11, backward with cost 00 — means a single outward walk from city 00 counts exactly the edges pointing the wrong way.

Time $O(n)$ . Space $O(n)$ .

Why it is correct: because the underlying graph is a tree, there is exactly one path between city 00 and every other city. Walking outward from 00, each edge is crossed in the direction away from 00 — which is the direction traffic must be able to travel toward 00. So an edge whose original orientation matches the outward direction is pointing away from 00 and must be reversed; that is precisely the cost-11 case.

(3, [[1,0],[2,0]])(3, [[1,0],[2,0]]) gives 00: both roads already point at city 00.

Attempting this by building only the directed adjacency and searching for what can reach 00 is much harder — the undirected-walk-with-costs reframing is what makes it a five-line traversal.

Follow-ups: “What if it were not a tree?” — multiple paths would exist and the problem becomes a min-cost orientation problem, far harder. “Make everything reachable from 0 instead?” — flip the cost assignment. “Recursive version?” — fine at 5 * 10^45 * 10^4? No — a path-shaped tree would exceed the recursion limit, so keep the explicit stack.

LC 802 — Find Eventual Safe States · Medium

Problem. A node is safe if every possible path starting from it leads to a terminal node (one with no outgoing edges). Return all safe nodes in ascending order.

Constraints. 1 <= n <= 10^41 <= n <= 10^4, no duplicate edges.

Examples. graph = [[1,2],[2,3],[5],[0],[5],[],[]]graph = [[1,2],[2,3],[5],[0],[5],[],[]] gives [2,4,5,6][2,4,5,6] · graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] gives [4][4]

Editorial

Reframe it: a node is unsafe exactly when some path from it enters a cycle. So this is cycle detection, reported per starting node.

Three-colour DFS is the standard tool for cycles in a directed graph:

0 (white) — not yet visited.
1 (grey) — currently on the recursion stack. Reaching a grey node means you have looped back onto your own path, which is a cycle.
2 (black) — fully explored and confirmed safe.

A two-colour visited set is not enough: revisiting a finished node is fine, but revisiting an in-progress node is a cycle. Distinguishing those two cases is exactly what the third colour buys, and it is why undirected cycle detection (where a parent check suffices) does not transfer.

Time $O(V + E)$ thanks to memoisation — each node is resolved once. Space $O(V)$ .

Note that nodes left grey when a FalseFalse propagates are never reset to white. That is deliberate: they reached a cycle, so they are permanently unsafe, and state[node] == 2state[node] == 2 correctly reports them as such.

Terminal nodes (5 and 6 in the first example) are trivially safe — the loop over their successors does not execute.

Follow-ups: “Do it with topological sort?” — yes: reverse the edges and run Kahn’s algorithm from the terminal nodes; whatever gets processed is safe. That is arguably cleaner and worth offering. “Just detect whether any cycle exists (LC 207)?” — the same three colours, stopping at the first grey hit. “Undirected graph?” — a parent check replaces the third colour.

LeetCode problem set

#	Problem	Difficulty	The twist
200	Number of Islands	Medium	Flood fill each unvisited land cell, count how many times a new fill starts
547	Number of Provinces	Medium	Component counting on an adjacency matrix instead of a list
323	Number of Connected Components in an Undirected Graph	Medium · Premium	Component counting straight from an edge list, the template this lesson opened with
733	Flood Fill	Easy	Recolor one connected region given a starting pixel
695	Max Area of Island	Medium	Flood fill that returns a size instead of just marking cells visited, tracking the max across all islands

Recap

Counting components = loop over every node, and for each unvisited one, run a full traversal and increment a counter.
The same idea works on an edge list, an adjacency matrix, or an implicit grid graph — only the “get neighbors” step changes.
Recursive DFS risks RecursionErrorRecursionError on deep/chain-shaped graphs; swap in an explicit stack when the input could be adversarial.
Multi-source BFS seeds the queue with every source at distance 0 up front — one traversal computes “distance to nearest source” for every node at once.

Next: Shortest Paths — Dijkstra, Bellman-Ford, and Floyd-Warshall, for when edges carry different weights and BFS’s “first arrival = shortest” guarantee no longer holds.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Graph Traversal and Connected Components

What you’ll learn

Quick recap: BFS and DFS

Connected components in an undirected graph

Recursion limits: prefer iterative DFS

Components on other representations

Multi-source BFS: distance to the nearest source

Complexity

Practice — real LeetCode problems

LC 1971 — Find if Path Exists in Graph · Easy

LC 1466 — Reorder Routes to Make All Paths Lead to the City Zero · Medium

LC 802 — Find Eventual Safe States · Medium

LeetCode problem set

Recap

Was this page helpful?