Graphs: BFS, DFS, and Topological Order

Most graph interview questions are BFS, DFS, or topological sort. The scoring is on choosing correctly between them and on handling the visited set properly.

Representations

from collections import defaultdict, deque
import heapq

edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]

adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)                 # undirected — both directions

n = 5
matrix = [[0]*n for _ in range(n)]
for u, v in edges:
    matrix[u][v] = matrix[v][u] = 1

print("adjacency list:", dict(adj))
print("matrix row 3:  ", matrix[3])

adjacency list: {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
matrix row 3:   [0, 1, 1, 0, 1]

“Almost every interview graph is sparse, so an adjacency list. A matrix on a million nodes would be a trillion cells.”

BFS gives the shortest path; DFS does not

def bfs_shortest(adj, start, goal):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, dist = q.popleft()
        if node == goal:
            return dist
        for nxt in adj[node]:
            if nxt not in seen:
                seen.add(nxt)                    # mark on ENQUEUE, not on dequeue
                q.append((nxt, dist + 1))
    return -1

def dfs_any_path(adj, start, goal, seen=None):
    seen = seen or {start}
    if start == goal:
        return 0
    for nxt in adj[start]:
        if nxt not in seen:
            seen.add(nxt)
            d = dfs_any_path(adj, nxt, goal, seen)
            if d != -1:
                return d + 1
    return -1

print(f"BFS 0→4: {bfs_shortest(adj, 0, 4)} edges")
print(f"DFS 0→4: {dfs_any_path(adj, 0, 4)} edges  ← a path, not necessarily the shortest")

BFS 0→4: 3 edges
DFS 0→4: 3 edges  ← a path, not necessarily the shortest

They agree here. Build a graph where they do not:

adj2 = defaultdict(list)
for u, v in [(0,1), (1,2), (2,3), (3,9), (0,9)]:
    adj2[u].append(v); adj2[v].append(u)

print(f"BFS 0→9: {bfs_shortest(adj2, 0, 9)} edges")
print(f"DFS 0→9: {dfs_any_path(adj2, 0, 9)} edges  ← wrong for a shortest-path question")

BFS 0→9: 1 edges
DFS 0→9: 4 edges  ← wrong for a shortest-path question

DFS wandered down the long branch first and returned 4 for a path of length 1.

“BFS explores by distance, so the first time it reaches a node is via the fewest edges. DFS commits to one branch, so the first path it finds is arbitrary. For unweighted shortest path it has to be BFS.”

Mark visited on enqueue, not on dequeue. Marking on dequeue lets the same node be queued many times before it is processed:

def bfs_mark_late(adj, start, goal):
    q, seen, enqueued = deque([(start, 0)]), set(), 0
    while q:
        node, dist = q.popleft()
        if node in seen: continue
        seen.add(node)                            # too late
        if node == goal: return dist, enqueued
        for nxt in adj[node]:
            if nxt not in seen:
                q.append((nxt, dist + 1)); enqueued += 1
    return -1, enqueued

def bfs_mark_early(adj, start, goal):
    q, seen, enqueued = deque([(start, 0)]), {start}, 0
    while q:
        node, dist = q.popleft()
        if node == goal: return dist, enqueued
        for nxt in adj[node]:
            if nxt not in seen:
                seen.add(nxt); q.append((nxt, dist + 1)); enqueued += 1
    return -1, enqueued

print(f"mark on dequeue: {bfs_mark_late(adj, 0, 4)}  (dist, nodes enqueued)")
print(f"mark on enqueue: {bfs_mark_early(adj, 0, 4)}")

mark on dequeue: (3, 6)  (dist, nodes enqueued)
mark on enqueue: (3, 4)

Same answer, more work. On a dense graph the late-marking version can enqueue O(E) copies and blow up memory.

Grids are graphs

def count_islands(grid):
    if not grid: return 0
    rows, cols, seen, count = len(grid), len(grid[0]), set(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in seen:
                count += 1
                stack = [(r, c)]                  # iterative — no recursion limit
                seen.add((r, c))
                while stack:
                    cr, cc = stack.pop()
                    for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
                        nr, nc = cr+dr, cc+dc
                        if (0 <= nr < rows and 0 <= nc < cols
                                and grid[nr][nc] == 1 and (nr, nc) not in seen):
                            seen.add((nr, nc)); stack.append((nr, nc))
    return count

grid = [[1,1,0,0,0],
        [1,1,0,0,1],
        [0,0,1,0,1],
        [0,0,0,1,1]]
print(f"islands: {count_islands(grid)}")
print(f"empty:   {count_islands([])}")

islands: 3
empty:   0

Neighbours are computed from coordinates rather than stored. Two things to say:

“A grid is a graph with implicit adjacency — each cell has up to four neighbours. I’m using an explicit stack rather than recursion because a 1000×1000 grid of all-ones would be a million-deep recursion and Python’s limit is 1000.”

Shortest path through a maze is the BFS version of the same thing:

def maze_shortest(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    q, seen = deque([(start, 0)]), {start}
    while q:
        (r, c), d = q.popleft()
        if (r, c) == goal: return d
        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 grid[nr][nc] == 0 and (nr, nc) not in seen):
                seen.add((nr, nc)); q.append(((nr, nc), d + 1))
    return -1

maze = [[0,0,0,1,0],
        [1,1,0,1,0],
        [0,0,0,0,0],
        [0,1,1,1,0],
        [0,0,0,0,0]]
print(f"(0,0)→(4,4): {maze_shortest(maze, (0,0), (4,4))} steps")
print(f"unreachable: {maze_shortest([[0,1],[1,0]], (0,0), (1,1))}")

(0,0)→(4,4): 8 steps
unreachable: -1

Cycle detection: directed and undirected differ

def has_cycle_undirected(adj, n):
    seen = set()
    def dfs(node, parent):
        seen.add(node)
        for nxt in adj[node]:
            if nxt == parent:                     # the edge we came in on — not a cycle
                continue
            if nxt in seen or dfs(nxt, node):
                return True
        return False
    return any(dfs(v, -1) for v in range(n) if v not in seen)

tree = defaultdict(list)
for u, v in [(0,1), (1,2), (1,3)]:
    tree[u].append(v); tree[v].append(u)
cyclic = defaultdict(list)
for u, v in [(0,1), (1,2), (2,0)]:
    cyclic[u].append(v); cyclic[v].append(u)

print(f"tree has cycle:   {has_cycle_undirected(tree, 4)}")
print(f"triangle:         {has_cycle_undirected(cyclic, 3)}")

tree has cycle:   False
triangle:         True

The nxt == parent skip is essential — without it, every undirected edge looks like a two-node cycle.

Directed graphs need a different idea: is this node still on the current path?

def has_cycle_directed(adj, n):
    WHITE, GREY, BLACK = 0, 1, 2                  # unvisited / in progress / finished
    colour = [WHITE] * n
    def dfs(u):
        colour[u] = GREY
        for v in adj[u]:
            if colour[v] == GREY:                 # back edge to something in progress
                return True
            if colour[v] == WHITE and dfs(v):
                return True
        colour[u] = BLACK
        return False
    return any(colour[v] == WHITE and dfs(v) for v in range(n))

dag = defaultdict(list); dag[0] += [1, 2]; dag[1] += [3]; dag[2] += [3]
dcy = defaultdict(list); dcy[0] += [1]; dcy[1] += [2]; dcy[2] += [0]

print(f"DAG (diamond):  {has_cycle_directed(dag, 4)}   ← two paths to 3 is NOT a cycle")
print(f"directed cycle: {has_cycle_directed(dcy, 3)}")

DAG (diamond):  False   ← two paths to 3 is NOT a cycle
directed cycle: True

“In a directed graph, reaching an already-finished node is fine — that is just a second path to it, as in the diamond. Only reaching a node still on the current recursion stack is a cycle. A single visited set cannot distinguish those two cases, which is why three colours.”

That distinction is the question. A candidate who uses one visited set reports a cycle on the diamond.

Topological sort, two ways

def topo_kahn(adj, n):
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    out = []
    while q:
        u = q.popleft()
        out.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return out if len(out) == n else []            # short output ⇒ there was a cycle

def topo_dfs(adj, n):
    seen, out = set(), []
    def dfs(u):
        seen.add(u)
        for v in adj[u]:
            if v not in seen:
                dfs(v)
        out.append(u)                              # post-order: after all descendants
    for v in range(n):
        if v not in seen:
            dfs(v)
    return out[::-1]

courses = defaultdict(list)
for pre, post in [(0,1), (0,2), (1,3), (2,3), (3,4)]:
    courses[pre].append(post)

print(f"Kahn: {topo_kahn(courses, 5)}")
print(f"DFS:  {topo_dfs(courses, 5)}")
print(f"cyclic input → {topo_kahn(dcy, 3)}   ← empty means unschedulable")

Kahn: [0, 1, 2, 3, 4]
DFS:  [0, 2, 1, 3, 4]
cyclic input → []   ← empty means unschedulable

Both valid — a topological order is not unique. The practical difference:

“Kahn’s is iterative, so no recursion limit, and it detects a cycle for free: if the output is shorter than the node count, some nodes never reached in-degree zero, which means a cycle. That makes it the better answer to ‘can these courses be completed?’. The DFS version is shorter to write and needs a separate cycle check.”

Weighted: Dijkstra

def dijkstra(adj_w, start, n):
    dist = [float("inf")] * n
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                               # stale entry — already improved
        for v, w in adj_w[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

wadj = defaultdict(list)
for u, v, w in [(0,1,4), (0,2,1), (2,1,2), (1,3,1), (2,3,5)]:
    wadj[u].append((v, w)); wadj[v].append((u, w))

print(f"distances from 0: {dijkstra(wadj, 0, 4)}")
print(f"BFS would say 0→1 is 1 edge; the cheapest route is 0→2→1 costing 3")

distances from 0: [0, 3, 1, 4]
BFS would say 0→1 is 1 edge; the cheapest route is 0→2→1 costing 3

Two points worth making: BFS is Dijkstra with all weights equal to 1, and Dijkstra fails on negative weights — the greedy assumption that a popped node is final no longer holds, and you need Bellman-Ford.

The if d > dist[u]: continue line is the lazy-deletion idiom — heapq has no decrease-key, so stale entries are left in the heap and skipped on pop.

Union-Find, for connectivity

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                          # already connected — this edge is a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

uf = UnionFind(6)
for a, b in [(0,1), (1,2), (3,4)]:
    uf.union(a, b)
print(f"components: {uf.count}")
print(f"0 and 2 connected: {uf.find(0) == uf.find(2)}")
print(f"0 and 3 connected: {uf.find(0) == uf.find(3)}")
print(f"adding edge (0,2) creates a cycle: {not uf.union(0, 2)}")

components: 3
0 and 2 connected: True
0 and 3 connected: False
adding edge (0,2) creates a cycle: True

“Union-Find is the right answer when edges arrive incrementally and the question is ‘are these connected?’ — it is near-constant per operation with path compression and union by rank. DFS would need a full re-traversal after each edge. It is also the basis of Kruskal’s minimum spanning tree, and union returning False is a cycle detector for undirected graphs.”

Bipartite check — colouring during BFS

def is_bipartite(adj, n):
    colour = {}
    for start in range(n):
        if start in colour: continue
        colour[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in colour:
                    colour[v] = 1 - colour[u]
                    q.append(v)
                elif colour[v] == colour[u]:
                    return False                  # neighbours share a colour
    return True

square = defaultdict(list)
for u, v in [(0,1), (1,2), (2,3), (3,0)]:
    square[u].append(v); square[v].append(u)

print(f"4-cycle bipartite:  {is_bipartite(square, 4)}")
print(f"triangle bipartite: {is_bipartite(cyclic, 3)}")

4-cycle bipartite:  True
triangle bipartite: False

A graph is bipartite exactly when it has no odd-length cycle — which is what the colouring detects.

Recognising it

SIGNAL                                        REACH FOR
"shortest path", unweighted                   BFS
"is there a path", "count regions"            DFS / union-find
grid, maze, islands, flood fill               BFS/DFS with computed neighbours
"prerequisites", "build order", "schedule"    topological sort (Kahn's)
"can this be completed" / deadlock            topological sort — empty output = cycle
"shortest path" with weights                  Dijkstra
negative weights                              Bellman-Ford, not Dijkstra
edges arriving one at a time, connectivity    union-find
"two groups", "no two adjacent the same"      bipartite colouring

Complexity

BFS / DFS            O(V + E) time, O(V) space
Topological sort     O(V + E)
Dijkstra (binary heap) O((V + E) log V)
Union-Find           ~O(1) amortised per op (inverse Ackermann)
Grid traversal       O(rows × cols)

The checklist

print(bfs_shortest(defaultdict(list), 0, 0))     # single node, start == goal
print(count_islands([[0,0],[0,0]]))              # no islands
print(topo_kahn(defaultdict(list), 3))           # no edges — every order is valid
print(maze_shortest([[0]], (0,0), (0,0)))
print(is_bipartite(defaultdict(list), 2))        # disconnected

0
0
[0, 1, 2]
0
True

Disconnected components are the one most often missed — every traversal needs an outer loop over all nodes, not just a call from node 0.

Practice

BFS 0→9: 1 edge     DFS 0→9: 4 edges

mark on dequeue: 6 nodes enqueued
mark on enqueue: 4 nodes enqueued

DAG (diamond): False   ← two paths to one node is not a cycle

[]   ← output shorter than n means a cycle

Next: sorting, searching and heaps — including the binary search with no sorted array.