Graph Algorithms8 min read

BFS & DFS Revisited

Two ways to explore a graph — level by level, or all the way in
BFS:\(O(V+E)\)DFS:\(O(V+E)\)space:\(O(V)\)

Imagine you're lost in a maze. You have two strategies:

BFS (Breadth-First Search) — you send out scouts in every direction simultaneously. First they check every spot one step away. Then every spot two steps away. Then three. You explore level by level, like ripples in a pond.

DFS (Depth-First Search) — you pick one corridor and follow it as far as it goes. Hit a dead end? Backtrack to the last junction and try another path. You go deep before going wide.

Both strategies visit every reachable node exactly once. But the order in which they visit nodes is completely different — and that order determines which problems each one solves best.

Breadth-First Search

BFS uses a queue (first-in, first-out). You enqueue the start node, mark it visited, then repeatedly dequeue a node and enqueue all its unvisited neighbors.

Because nodes are processed in order of how far they are from the start, BFS naturally finds the shortest path in an unweighted graph. The first time BFS reaches a node, it has used the fewest possible edges.

Classic uses: shortest path in unweighted graphs, level-order traversal, bipartiteness check (2-coloring), finding connected components.

Depth-First Search

DFS uses a stack — either an explicit one or the call stack via recursion. You push the start node, then always process the most recently discovered unvisited node.

DFS assigns each node a discovery time (when it was first visited) and a finish time (when all its descendants were fully explored). These timestamps reveal the structure of the graph.

Classic uses: topological sort, cycle detection, finding strongly connected components (Tarjan's), detecting bridges and articulation points.

BFS and Shortest Paths

In an unweighted graph, BFS guarantees that when node v is first dequeued, dist[v] holds the true shortest distance from the source. Why? Because BFS processes all nodes at distance d before any at distance d+1. Any path of length d+1 must first pass through a node at distance d.

DFS Timestamps and What They Tell You

DFS timestamps obey the parenthesis theorem: for any two nodes u and v, their active intervals (disc[u] to fin[u] and disc[v] to fin[v]) are either completely nested or completely disjoint — never partially overlapping. This means:

  • Back edge (to an ancestor already on the stack) → cycle detected
  • Decreasing finish times → topological order for a DAG
  • low-link values (from Tarjan's) → SCCs and bridges

Bipartiteness Check

A graph is bipartite if you can color every node either red or blue so that no two adjacent nodes share the same color. BFS makes this easy: color the source red, color all its neighbors blue, color their neighbors red, and so on. If you ever need to color a node a different color than it already has, the graph is not bipartite (it has an odd-length cycle).

Note: BFS = use a queue, find shortest paths. DFS = use a stack (or recursion), find structure. When in doubt about which to use: need shortest path? BFS. Need to explore the full shape of the graph? DFS.

BFS (shortest path) and DFS (cycle detection)

from collections import deque


def bfs_shortest(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


def dfs_has_cycle(graph, n):
    # 0=unvisited, 1=in-stack, 2=done
    color = [0] * n
    def dfs(u):
        color[u] = 1
        for v in graph[u]:
            if color[v] == 1:
                return True   # back edge = cycle
            if color[v] == 0 and dfs(v):
                return True
        color[u] = 2
        return False
    return any(dfs(u) for u in range(n) if color[u] == 0)


graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
print(bfs_shortest(graph, 0))  # {0:0, 1:1, 2:1, 3:2}


cyclic = [[1], [2], [0]]       # 0->1->2->0
print(dfs_has_cycle(cyclic, 3))  # True
Output
{0: 0, 1: 1, 2: 1, 3: 2}
True

Complexity

🌊 BFS traversalEach vertex enqueued once, each edge examined once
Linear in graph size\(O(V+E)\)
🔍 DFS traversalEach vertex and edge visited exactly once
Linear in graph size\(O(V+E)\)
📦 BFS space (queue)Worst case: all vertices at the same distance (star graph)
Up to one full level\(O(V)\)
📚 DFS space (stack)Recursion depth = longest path; worst case \(O(V)\) for a path graph
Proportional to graph depth\(O(V)\)
🎨 Bipartiteness checkOne BFS with 2-coloring — contradiction means odd cycle = not bipartite
Single pass\(O(V+E)\)
🏝️ Connected componentsRun BFS/DFS from each unvisited vertex; each component found once
Full graph traversal\(O(V+E)\)

Quick check

You want the shortest path between two nodes in an unweighted graph. Which algorithm should you use?

Continue reading

Topological Sort
Order tasks by their dependencies — no chicken-before-egg
→
Dijkstra's Algorithm
Always extend the cheapest road first — GPS navigation for graphs
→
DP on Trees
Each node's answer depends on its children — compute bottom-up
→