Lesson 9 of 10 · 11 min

Graphs: traversal, ordering and connectivity

Recognise a graph problem in disguise, pick BFS or DFS deliberately, and handle cycles and dependencies.

Spotting a graph

Many problems are graphs without saying so. A grid is a graph where each cell connects to its neighbours. Course prerequisites are a directed graph. Word ladders connect words differing by one letter. Once you see the nodes and edges, the algorithm is usually standard.

Representation matters: an adjacency list costs O(V + E) and suits sparse graphs; an adjacency matrix costs O(V²) regardless but answers 'is there an edge?' instantly.

Choosing a traversal

Need	Use	Why
Fewest steps, equal edge costs	BFS	Explores by distance, so the first arrival is shortest
Reachability, components, cycles	DFS	Follows structure and backtracks naturally
Dependency ordering	Topological sort	Only exists for a DAG; a short result proves a cycle
Shortest path, weighted edges	Dijkstra	Greedy expansion with a priority queue
Connectivity under merging	Union-find	Near-constant amortised joins and queries

BFS on a grid, with the mistake that ruins it

from collections import deque

def shortest(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(0, 0, 1)])
    seen = {(0, 0)}                    # mark on PUSH, not on pop
    while queue:
        r, c, dist = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return dist
        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))
                queue.append((nr, nc, dist + 1))
    return -1

Note: Marking visited on pop lets the same cell be queued once per incoming edge, which degrades badly on dense graphs.

Cycle detection is direction-dependent

In an undirected graph, reaching an already-visited node that is not your parent means a cycle. Union-find also works: an edge joining two nodes already in the same set closes a cycle.

In a directed graph a visited boolean is not enough. Reaching a node you have already finished is fine — it just means a shared descendant. Only reaching a node still on the current recursion stack is a cycle, which is why you need three states: unvisited, in progress, done.

Topological sort, which also detects cycles

from collections import deque

def topo_order(n, edges):        # edges are (before, after)
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1

    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == n else []   # short result means a cycle

Worth remembering

Grids, dependencies and word transformations are all graphs.
BFS gives shortest paths on unit edges; DFS explores structure.
Directed cycle detection needs three states, not a visited boolean.

Test it now

Graph modelling questions are concentrated in the hard bank.

Hard DSA quiz →All levels