Graph DFS and BFS

Problem

The input is a set of nodes and connections: an explicit list of edges, a grid, a set of words that differ by one letter, bus routes, or the states of a lock. You are asked what is reachable, how many separate pieces there are, whether there is a loop, how far apart two nodes are, or to copy the whole structure. The data may not look like a graph at all; the work is spotting the nodes and the neighbor rule.

Intuition

Explore a cave with a ball of string and a piece of chalk. The chalk marks rooms you have entered, so you never walk in circles; the string lets you retreat. Going deep first means following one tunnel until it dead-ends, then returning along the string to the last fork. Going broad first means checking every room one step away, then every room two steps away, and so on, which is why the first time breadth-first search touches a room, it got there in the fewest steps.

The data structure behind each is the only real difference. Depth-first uses a stack (the call stack does it for you in a recursive version): the most recent discovery is explored next. Breadth-first uses a queue: the oldest discovery is explored next. The chalk is a visited set, and forgetting it turns a graph search into an infinite loop the moment the graph has a cycle.

The small number beside a node is when it was visited. Green nodes were reached from node 0; grey nodes (5 and 6) sit in another component and are never touched. The diagram scrolls sideways on a narrow screen.

Mechanics

Representing the graph

An adjacency list maps each node to its neighbors and takes O(V + E) space; it is the default. For an undirected edge, add each endpoint to the other's list. A matrix costs O(V²) and only pays off for dense graphs. When the graph is implicit (grids, words, lock positions), a function that yields neighbors takes the place of the list.

The invariant

Mark a node visited when you add it to the stack or queue, not when you take it out. Then every node enters the frontier at most once, so the work is O(V + E). The search stops when the frontier is empty, and at that point every node reachable from the start is visited: if some reachable node were not, take a shortest path to it, and the first unvisited node on that path would have been added when its visited predecessor was processed, a contradiction.

Why BFS gives shortest paths

The queue holds nodes in nondecreasing distance: all nodes at distance d are dequeued before any at distance d + 1, because nodes at d + 1 are only appended while processing nodes at d. A node is therefore first discovered by the earliest possible parent, and its recorded distance is minimal. This needs every edge to cost the same.

Components and cycles

Loop over all nodes and start a search from each unvisited one: the number of starts is the number of connected components. For cycles, undirected graphs are easy (a visited neighbor that is not the parent you came from closes a loop). Directed graphs need three states: unseen, on the current path, finished. An edge to a node that is on the current path is a cycle; an edge to a finished node is not.

Each column is one ring of the search. A node's column is its shortest distance from node 0, and the queue always finishes a column before it starts the next.

Worked example

The graph has 7 nodes and edges 0-1, 0-2, 1-3, 2-3, 3-4, 5-6. Neighbors are tried in increasing order.

BFS distances from node 0 are 0: 0, 1: 1, 2: 1, 3: 2, 4: 3. Node 4 is 3 steps away, and DFS happens to visit node 3 before node 2 even though 2 is closer to the start, which is why DFS cannot answer shortest-path questions.

Components. Starting fresh from every unvisited node finds 2 components: {0, 1, 2, 3, 4}, {5, 6}.

A directed cycle. With edges 0→1, 1→2, 2→3, 2→4, 3→1, the three-state search reaches node 3, sees that its edge to 1 points at a node still on the path, and reports the cycle 1 → 2 → 3 → 1. Remove the edge 3→1 and it reports none.

An implicit graph. Turning "cat" into "dog" one letter at a time, using only the words cot, cog, dot, bat, cut, dog, BFS finds the sequence cat → cot → dot → dog (3 changes) after taking 7 words off the queue. Keep only "cot" and "dog" and it correctly reports no sequence after 2 words. The target must be in the word list: without "dog" there is no sequence at all, so the word list, not the target, decides which words are nodes.

Cloning. Copying the component of node 3 assigns fresh ids in discovery order; the old-to-new map is 3→0, 1→1, 2→2, 4→3, 0→4. The copy has the same shape, since every old edge is translated through the map.

Implementation

from collections import deque


def dfs(adj, start):
    seen = {start}
    order = []

    def visit(node):
        order.append(node)
        for nxt in adj[node]:
            if nxt not in seen:
                seen.add(nxt)
                visit(nxt)

    visit(start)
    return order


def bfs_distances(adj, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in adj[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist


def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * n
    count = 0
    for root in range(n):
        if seen[root]:
            continue
        count += 1
        seen[root] = True
        stack = [root]
        while stack:
            node = stack.pop()
            for nxt in adj[node]:
                if not seen[nxt]:
                    seen[nxt] = True
                    stack.append(nxt)
    return count

Variations and edge cases

def has_cycle(adj):
    UNSEEN, ON_PATH, DONE = 0, 1, 2
    state = {node: UNSEEN for node in adj}

    def visit(node):
        state[node] = ON_PATH
        for nxt in adj[node]:
            if state[nxt] == ON_PATH:
                return True
            if state[nxt] == UNSEEN and visit(nxt):
                return True
        state[node] = DONE
        return False

    return any(state[node] == UNSEEN and visit(node) for node in adj)


def clone(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for nxt in cur.neighbors:
            if nxt not in copies:
                copies[nxt] = Node(nxt.val)
                queue.append(nxt)
            copies[cur].neighbors.append(copies[nxt])
    return copies[node]


def ladder_length(begin, end, words):
    buckets = {}
    for w in set(words) | {begin}:
        for i in range(len(w)):
            buckets.setdefault(w[:i] + "*" + w[i + 1:], []).append(w)
    queue, dist = deque([begin]), {begin: 1}
    while queue:
        w = queue.popleft()
        if w == end:
            return dist[w]
        for i in range(len(w)):
            for nxt in buckets[w[:i] + "*" + w[i + 1:]]:
                if nxt not in dist:
                    dist[nxt] = dist[w] + 1
                    queue.append(nxt)
    return 0

• Marking too late. Marking a node visited when it is popped lets it be added many times; on a dense graph the queue explodes. Mark on push.
• Recursion depth. Python stops near 1000 frames. A path-like graph with 100,000 nodes needs an explicit stack, or sys.setrecursionlimit with care.
• Undirected cycles. Every edge appears twice, so ignore the parent you arrived from (by id, not by value, if parallel edges are possible). A valid tree on n nodes has exactly n - 1 edges and one component.
• Deque, not list. list.pop(0) is O(n); the queue needs deque.popleft().
• Implicit graphs. Bucketing words by wildcard pattern turns an O(N²) all-pairs comparison into O(N·L) buckets. A state space such as a 4-digit lock has 10,000 nodes and eight neighbors each.
• Edge cases: an empty graph, a single node with a self-loop, a disconnected target (return a clear "unreachable"), start equal to target, and duplicate edges.

Complexity and tradeoffs

• Time: O(V + E): each node enters the frontier once and each adjacency entry is read once (twice for undirected edges). An implicit graph costs the number of states times the work to generate neighbors.
• Space: O(V) for the visited set and frontier, plus the adjacency list. DFS may use O(depth) stack, which is small on bushy graphs and V on a chain; BFS holds a whole ring, which is largest on wide graphs.
• Baseline. Trying all paths between two nodes is exponential. The visited set is what removes it.
• BFS or DFS. Fewest steps in an unweighted graph: BFS. Any path, components, cycles, or exploring everything with a stack-friendly structure: DFS. Both work for reachability and component counts.
• When it fails. Weighted edges need Dijkstra or Bellman-Ford. Repeated connectivity questions with edge additions suit union-find. Dependencies between tasks suit topological sort. A huge state space can need bidirectional search to stay tractable.

Problems

Clone Graph is the purest traversal-with-a-map exercise. Word Ladder, Open the Lock, Minimum Knight Moves and Bus Routes all hide a graph behind a rule and ask for fewest steps: BFS from the start. Evaluate Division treats variables as nodes and ratios as edge weights multiplied along a path. Find the Town Judge is a counting variant of the same graph vocabulary (in-degree and out-degree).

Easy

• 997. Find the Town Judge NeetCode 250
  The judge's in-degree minus out-degree is n-1, a property no other person can have.

Medium

• 133. Clone Graph Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Map each original node to its copy during the traversal, so cycles reuse copies instead of looping forever.
• 399. Evaluate Division NeetCode 250
  Each equation is a weighted edge in both directions, so a query is the product of weights along any path between its two variables.
• 752. Open the Lock NeetCode 250
  Each lock state is a node with eight neighbours, so BFS from 0000 while skipping dead ends finds the fewest turns.
• 1197. Minimum Knight Moves Grind 169
  BFS outward from the origin over knight moves; symmetry lets you search one quadrant with a small margin around it.

Hard

• 127. Word Ladder Grind 169 NeetCode 150 NeetCode 250
  Words are nodes joined when they differ by one letter, so the shortest transformation is a BFS, with wildcard patterns finding neighbours quickly.
• 815. Bus Routes Grind 169
  Run BFS over bus routes rather than stops, mapping each stop to the routes through it and counting buses taken.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 207. Course Schedule Medium
• 210. Course Schedule II Medium
• 261. Graph Valid Tree Medium
• 279. Perfect Squares Medium
• 310. Minimum Height Trees Medium
• 323. Number of Connected Components in an Undirected Graph Medium
• 721. Accounts Merge Medium
• 863. All Nodes Distance K in Binary Tree Medium
• 1462. Course Schedule IV Medium
• 269. Alien Dictionary Hard
• 332. Reconstruct Itinerary Hard

Connections

Tree DFS and BFS are these two searches on a graph with no cycles, where the visited set becomes unnecessary because there is only one path to each node. Grid graphs apply the same code to a matrix, topological sort extends DFS and BFS to directed acyclic graphs, and Dijkstra replaces the queue with a priority queue when edges have costs.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 20 (breadth-first and depth-first search, with the proofs of the distance and parenthesis properties).
• Sedgewick and Wayne, Algorithms, sections 4.1 and 4.2 (undirected and directed graphs).
• Skiena, The Algorithm Design Manual, chapter 7 on graph traversal.
• Moore, "The shortest path through a maze", 1959, the origin of breadth-first shortest-path search; Hopcroft and Tarjan, "Efficient algorithms for graph manipulation", 1973, for linear-time depth-first applications.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.