Graph Traversal: BFS, DFS & Applications

A graph G = (V, E) consists of a set of vertices V (also called nodes) and a set of edges E. In an undirected graph, each edge is an unordered pair {u, v}; in a directed graph (digraph), each edge is an ordered pair (u, v) meaning an arc from u to v.

The two standard representations are:

• Adjacency list: For each vertex u, store a list of its neighbors. Space: O(V + E). Time to iterate over all neighbors of u: O(deg(u)). This is the right choice for sparse graphs (E << V²).
• Adjacency matrix: A V × V matrix where A[u][v] = 1 if edge (u,v) exists. Space: O(V²). Time to check if (u,v) is an edge: O(1). Best for dense graphs.

For most graph algorithm analysis, we assume adjacency lists, which gives total traversal time O(V + E) — you touch each vertex once and each edge once (or twice for undirected).

Key vocabulary you must know:

• Path: sequence of vertices connected by edges.
• Cycle: a path where the first and last vertex are the same.
• Connected: an undirected graph is connected if there is a path between every pair of vertices.
• DAG: Directed Acyclic Graph — a directed graph with no directed cycles.
• Tree: a connected acyclic undirected graph (V-1 edges).
• Forest: a disjoint union of trees.

from collections import defaultdict

# Adjacency list representation
class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v):
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

# Example: build a small undirected graph
g = Graph()
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
    g.add_edge(u, v)
# g.adj[0] = [1, 2], g.adj[3] = [1, 2, 4]

The core idea: BFS explores a graph in waves outward from a source vertex s. First it visits all vertices at distance 1 from s, then all at distance 2, and so on. The mental model is a stone dropped in water — the ripple expands layer by layer. BFS uses a queue (FIFO) to enforce this ordering: you enqueue a vertex when you discover it, and dequeue to process it, enqueuing its unvisited neighbors.

The algorithm:

1. Initialize: mark s as visited, enqueue s, set dist[s] = 0.
2. While queue is non-empty: dequeue u. For each neighbor v of u: if v is unvisited, mark v visited, set dist[v] = dist[u] + 1, record parent[v] = u, enqueue v.

Why does this give shortest paths? Because BFS processes vertices in non-decreasing order of distance. When vertex v is first discovered through edge (u, v), no shorter path to v can exist — if one did, v would have been discovered earlier (at a smaller distance). This is a proof by induction on the distance layers.

Time complexity: O(V + E). Each vertex is enqueued and dequeued at most once — O(V). Each edge (u, v) is examined when u is dequeued — O(E) total.

Space complexity: O(V) for the queue, dist[], and parent[] arrays.

The BFS tree: The parent[] array defines a spanning tree (or forest) rooted at s. Every tree edge goes from a vertex to a newly-discovered neighbor. Non-tree edges in an undirected graph connect vertices within the same layer or adjacent layers — they are called cross edges in BFS.

from collections import deque

def bfs(graph, source, n):
    dist = [-1] * n          # -1 = unvisited
    parent = [-1] * n
    dist[source] = 0
    queue = deque([source])

    while queue:
        u = queue.popleft()
        for v in graph.adj[u]:
            if dist[v] == -1:    # unvisited
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)

    return dist, parent

def reconstruct_path(parent, source, target):
    """Trace back through parent[] to get shortest path."""
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()
    # path[0] == source if target is reachable
    return path if path[0] == source else []

The core idea: DFS explores as far as possible along each branch before backtracking. The mental model is exploring a maze by always turning left and marking your path with chalk; you only backtrack when you hit a dead end or a visited node. DFS uses a stack — either explicitly or via the call stack in a recursive implementation.

Discovery and finish times: The key structural insight in DFS is the timestamp. Assign each vertex u two integers: disc[u] (when u is first visited) and finish[u] (when u's entire subtree has been explored and we backtrack from u). These timestamps define a nesting structure: for any two vertices u and v, either their intervals [disc, finish] are completely nested (one is an ancestor of the other in the DFS tree) or completely disjoint. This is the Parenthesis Theorem — one of the most important structural results in graph algorithms.

Edge classification (critical for applications): When running DFS on a directed graph, every edge (u, v) falls into exactly one of four categories:

• Tree edge: v was unvisited when (u, v) was explored. These form the DFS forest.
• Back edge: v is an ancestor of u in the DFS tree (disc[v] < disc[u] < finish[u] < finish[v]). Back edges indicate cycles.
• Forward edge: v is a descendant of u but (u,v) is not a tree edge (disc[u] < disc[v] < finish[v] < finish[u]).
• Cross edge: none of the above — v was already fully finished (finish[v] < disc[u]).

In undirected graphs, only tree edges and back edges exist (no forward or cross edges).

Time and space complexity: O(V + E) time, O(V) space for the recursion stack and color/visit arrays. Watch out: in Python, deep recursion on large graphs can hit the recursion limit — use an explicit stack for production code.

DFS on disconnected graphs: Always wrap DFS in a loop over all vertices to ensure full coverage of every connected component (or strongly connected component).

def dfs(graph, n):
    """
    Full DFS over all vertices; records disc/finish times
    and classifies edges for a directed graph.
    """
    WHITE, GRAY, BLACK = 0, 1, 2  # unvisited, in-stack, done
    color = [WHITE] * n
    disc   = [0] * n
    finish = [0] * n
    parent = [-1] * n
    timer = [0]          # mutable counter (closure trick)

    def dfs_visit(u):
        color[u] = GRAY
        timer[0] += 1
        disc[u] = timer[0]
        for v in graph.adj[u]:
            if color[v] == WHITE:
                parent[v] = u
                dfs_visit(v)          # tree edge
            elif color[v] == GRAY:
                pass                  # back edge -> cycle!
            # BLACK -> forward or cross edge
        color[u] = BLACK
        timer[0] += 1
        finish[u] = timer[0]

    for u in range(n):
        if color[u] == WHITE:
            dfs_visit(u)

    return disc, finish, parent

Both BFS and DFS produce a spanning forest of the graph: a set of trees that together touch every vertex. The structure of these trees reveals deep properties of the graph.

The BFS tree is the shallowest possible spanning tree rooted at the source. Every vertex appears at its true shortest-path distance from the source. The BFS tree is useful because paths in it are shortest paths in the original graph. Non-tree edges always connect vertices whose BFS layers differ by at most 1 (in undirected graphs). This means if you find a non-tree edge {u, v} where both are in the same layer, you have found an odd or even cycle, which is the basis of bipartite graph detection: a graph is bipartite if and only if BFS produces no non-tree edges within the same layer.

The DFS tree is deeper — it tends to produce long, chain-like trees. Its most important property is the Parenthesis Theorem: the disc/finish intervals for all vertices have a perfect nesting structure. This is what lets DFS detect cycles (back edges), perform topological ordering (vertices finish in reverse topological order), and find strongly connected components (Kosaraju/Tarjan).

A beautiful duality: BFS trees are wide and shallow, optimized for distance. DFS trees are tall and narrow, optimized for structural discovery. Choosing between them is about which geometric property of the graph you care about.

A topological ordering of a DAG is a linear ordering of vertices such that for every directed edge (u, v), u appears before v. Think of it as a valid build order: if task A must be completed before task B, A must come first. Topological sort is only defined for DAGs — the presence of a cycle makes it impossible (if A → B → C → A, who goes first?).

DFS-based algorithm (CLRS): Run DFS on the DAG. When a vertex finishes (gets its finish time), prepend it to a list. The resulting list is a topological ordering. Why? When edge (u, v) exists and v is not an ancestor of u (which it cannot be in a DAG — that would be a back edge/cycle), v finishes before u. So prepending in finish order gives u before v — exactly what we need.

Kahn's algorithm (BFS-based): Maintain the in-degree of every vertex. Initialize a queue with all vertices of in-degree 0. Repeatedly dequeue a vertex u, append it to the output, and for each neighbor v, decrement in-degree[v]; if it hits 0, enqueue v. If the output has fewer than V vertices, the graph has a cycle.

Kahn's has a bonus: it simultaneously checks for cycles. If the topological sort terminates with fewer than V vertices processed, there is a cycle (those vertices never reached in-degree 0).

Time complexity: O(V + E) for both algorithms.

from collections import deque

def topological_sort_kahn(graph, n):
    """Returns topological order or None if cycle detected."""
    indegree = [0] * n
    for u in range(n):
        for v in graph.adj[u]:
            indegree[v] += 1

    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph.adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return order if len(order) == n else None  # None = cycle

# DFS-based approach: collect finish-order in reverse
def topological_sort_dfs(graph, n):
    visited = [False] * n
    stack = []

    def dfs(u):
        visited[u] = True
        for v in graph.adj[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)  # append on finish

    for u in range(n):
        if not visited[u]:
            dfs(u)

    stack.reverse()
    return stack

Undirected graphs: A cycle exists if and only if DFS finds a back edge — an edge to a vertex that is currently on the DFS stack (color GRAY). Equivalently, a cycle exists if DFS produces any edge (u, v) where v is already visited and v is not u's direct parent in the DFS tree (otherwise every edge looks like a back edge in undirected graphs).

Directed graphs: Same rule — a cycle exists iff DFS finds a back edge (an edge to a GRAY vertex). A back edge to a BLACK vertex is a forward or cross edge and does NOT indicate a cycle. This distinction is crucial and a common source of bugs: in directed graphs, you must track the three-color state (WHITE/GRAY/BLACK), not just visited/unvisited.

Kahn's algorithm for directed graphs: After running Kahn's topological sort, if the output has fewer than V vertices, a cycle exists. This is often cleaner in practice.

Union-Find for undirected graphs: Another clean approach uses a Disjoint Set Union (DSU) structure. Process each edge; if both endpoints are already in the same component, adding the edge creates a cycle. This runs in O(E · α(V)) time, nearly O(E), and is used in Kruskal's MST algorithm for exactly this check.

Real-world relevance: Cycle detection is central to deadlock detection in operating systems (wait-for graph), detecting circular imports in Python/JavaScript build tools, and validating task dependencies in workflow schedulers.

def has_cycle_directed(graph, n):
    """True if the directed graph has a cycle."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def dfs(u):
        color[u] = GRAY
        for v in graph.adj[u]:
            if color[v] == GRAY:      # back edge -> cycle
                return True
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(dfs(u) for u in range(n) if color[u] == WHITE)


def has_cycle_undirected(graph, n):
    """True if the undirected graph has a cycle."""
    visited = [False] * n

    def dfs(u, parent):
        visited[u] = True
        for v in graph.adj[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:  # visited and not our parent
                return True    # back edge -> cycle
        return False

    return any(dfs(u, -1) for u in range(n) if not visited[u])

A connected component of an undirected graph is a maximal set of vertices such that every pair is connected by a path. To find all connected components, simply run BFS or DFS from every unvisited vertex — each call discovers exactly one complete component.

Algorithm: Maintain a component[] array. For each unvisited vertex u, run BFS/DFS from u and label all discovered vertices with the current component ID. Increment the component counter.

Time complexity: O(V + E) — each vertex and edge is touched exactly once across all calls.

Applications:

• Image segmentation: pixels are vertices, edges connect adjacent same-colored pixels; components are regions.
• Network reliability: is the network connected? How many components?
• Percolation theory: does a component span from top to bottom of a grid?

Online connectivity: If edges are added dynamically, Union-Find (DSU) maintains components in O(α(V)) per operation — far more efficient than re-running BFS/DFS after every insertion.

Bipartite checking: A graph is bipartite iff it has no odd-length cycle. You can check this during BFS/DFS: 2-color the graph. If you ever need to assign a vertex the same color as its neighbor, the graph is not bipartite.

def find_components(graph, n):
    """
    Returns (num_components, component_id[]) for undirected graph.
    component_id[v] = which component v belongs to.
    """
    from collections import deque
    component_id = [-1] * n
    num_components = 0

    for start in range(n):
        if component_id[start] != -1:
            continue
        # BFS from 'start'
        queue = deque([start])
        component_id[start] = num_components
        while queue:
            u = queue.popleft()
            for v in graph.adj[u]:
                if component_id[v] == -1:
                    component_id[v] = num_components
                    queue.append(v)
        num_components += 1

    return num_components, component_id


def is_bipartite(graph, n):
    """2-color attempt; returns False if odd cycle found."""
    from collections import deque
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph.adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    return True

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices such that there is a directed path from every vertex to every other vertex in the set. SCCs partition the vertices of any digraph.

If you condense each SCC to a single node, the result is a DAG — called the condensation of the graph. This is a profound insight: every directed graph decomposes into a DAG of strongly connected regions.

Kosaraju's algorithm (two-pass DFS, elegant and easy to prove):

1. Run DFS on the original graph G. Record finish times (or push onto a stack on finish).
2. Compute G^T — the transpose of G (reverse all edges).
3. Process vertices in decreasing order of finish time (pop from stack). Run DFS on G^T. Each DFS tree in this second pass is exactly one SCC.

Why does it work? If SCC C1 has an edge to SCC C2 in G, then in G^T the edge is reversed. The vertex in C1 with the latest finish time finishes after all of C2. So in pass 2, we reach C1 first, and from C1 on G^T we can only reach back within C1 (the edge to C2 is now reversed outward from C2). Each second-pass DFS tree stays within one SCC.

Tarjan's algorithm is a single-pass DFS that finds SCCs using a stack and low-link values (the earliest discovery time reachable from a subtree). It is equally O(V + E) and is often preferred in competitive programming.

Time complexity of Kosaraju's: O(V + E) — two DFS passes plus one graph reversal.

Applications: Web page ranking (SCCs of the link graph), compiler optimizations (detecting mutually recursive function groups), game solving (determining winning/losing positions in cyclic games).

from collections import defaultdict

def kosaraju(n, adj):
    """Returns list of SCCs (each SCC is a list of vertices)."""
    # Pass 1: DFS on original graph, record finish order
    visited = [False] * n
    finish_stack = []

    def dfs1(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs1(v)
        finish_stack.append(u)

    for u in range(n):
        if not visited[u]:
            dfs1(u)

    # Build transpose graph
    radj = defaultdict(list)
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    # Pass 2: DFS on transpose in reverse finish order
    visited2 = [False] * n
    sccs = []

    def dfs2(u, component):
        visited2[u] = True
        component.append(u)
        for v in radj[u]:
            if not visited2[v]:
                dfs2(v, component)

    while finish_stack:
        u = finish_stack.pop()
        if not visited2[u]:
            component = []
            dfs2(u, component)
            sccs.append(component)

    return sccs

Both BFS and DFS achieve O(V + E) time — this is optimal for graph traversal, since a correct algorithm must examine every vertex and every edge at least once (otherwise it might miss a component or misclassify an edge).

The accounting argument: In an adjacency-list representation, each vertex u is processed once (enqueued/dequeued in BFS, or called/returned in DFS). When processing u, we iterate over its adjacency list, which has length deg(u). The total work across all vertices is:

Σ_{u ∈ V} deg(u) = 2|E| (undirected) or |E| (directed)

plus O(V) for the vertex bookkeeping. Hence O(V + E).

Space complexity: BFS requires O(V) for the queue (in the worst case, an entire layer is in the queue — imagine a star graph where all V-1 leaves are enqueued at once). DFS requires O(V) for the recursion stack (in the worst case, a path graph causes V recursive calls). Both are O(V).

Why not O(V × E)? A naive implementation that, for each vertex, scans all edges to find neighbors would be O(VE). This happens with adjacency matrices when you want only the neighbors of u — you scan all V entries. For sparse graphs where E << V², the adjacency-list O(V + E) is dramatically better.

The tight lower bound: Any algorithm that determines reachability from a source must examine every edge reachable from that source — otherwise an adversary could insert or delete an edge it never saw and change the answer. So O(V + E) is not just what BFS/DFS achieve; it is what any correct traversal algorithm must achieve.

The recursive DFS is elegant, but in practice it can cause stack overflow for large graphs (Python's default recursion limit is 1000; a path graph of 10,000 vertices will crash it). The solution is to implement DFS with an explicit stack using a list or deque.

The subtlety: Naively replacing the recursion with a stack push all neighbors, then pop gives you something like DFS in terms of the vertices visited, but it does NOT correctly compute finish times or edge classification. The issue is that you need to know when you are returning from a vertex, not just when you first visit it.

The fix: Push (vertex, iterator_over_neighbors) onto the stack. When you pop a frame, you advance the iterator; when the iterator is exhausted, the vertex finishes.

Alternatively, for applications that only need to know which vertices are reachable (e.g., component detection) and not the exact DFS tree structure, the simple stack-based traversal suffices — and is much simpler to implement.

Key insight: The recursive DFS is beautiful for teaching because the call stack is the explicit stack. Understanding this equivalence helps you write correct iterative versions.

def dfs_iterative_reachability(graph, source, n):
    """Simple iterative DFS — correct for reachability."""
    visited = [False] * n
    stack = [source]
    visited[source] = True
    order = []

    while stack:
        u = stack.pop()
        order.append(u)
        for v in graph.adj[u]:
            if not visited[v]:
                visited[v] = True
                stack.append(v)
    return order


def dfs_iterative_with_finish(graph, source, n):
    """Iterative DFS that correctly computes finish order."""
    visited = [False] * n
    finished = [False] * n
    finish_order = []
    # stack holds (vertex, neighbor_index)
    stack = [(source, 0)]
    visited[source] = True

    while stack:
        u, idx = stack[-1]
        neighbors = graph.adj[u]
        if idx < len(neighbors):
            stack[-1] = (u, idx + 1)  # advance iterator
            v = neighbors[idx]
            if not visited[v]:
                visited[v] = True
                stack.append((v, 0))
        else:
            stack.pop()              # u is finished
            finish_order.append(u)
    return finish_order