Chapter 12: Graph Traversals

Navigating the Web of Data

In the previous chapter, we learned how to store graphs in memory using matrices and lists. However, a data structure is only as useful as the algorithms we can run on it. Graph Traversal is the fundamental process of visiting every vertex in a graph in a predictable, systematic order. Unlike trees, which have a single root and a clear hierarchy, graphs can be chaotic, cyclic, and disconnected. This means our traversal algorithms must be "smart" enough to avoid going in circles and robust enough to find every hidden corner of the network.

There are two primary ways to explore a graph: Breadth-First Search (BFS) and Depth-First Search (DFS). These two algorithms serve as the building blocks for nearly every complex graph operation, including finding the shortest path between cities, detecting cycles in dependencies, and even crawling the billions of pages on the World Wide Web. Understanding the mechanics of these traversals is the most important step in becoming an expert in graph theory.

Breadth-First Search (BFS): The Level-by-Level Ripple

Imagine dropping a pebble into a calm pond. The ripples move outward in perfect circles, hitting everything close to the center before reaching things further away. This is exactly how Breadth-First Search works. Starting from a chosen source vertex, BFS visits all the immediate neighbors first (the "Level 1" nodes). Only after every Level 1 node has been processed does the algorithm move on to their neighbors ("Level 2"). This "wide-before-deep" strategy ensures that the first time we reach a node, we have found the shortest possible path to it (assuming all edges have the same weight).

To implement this logic, we use a Queue data structure. A queue follows the "First-In, First-Out" (FIFO) principle, which perfectly maintains the level-by-order discovery. Crucially, because graphs can have cycles, we must maintain a Visited set or array. Every time we discover a new node, we mark it as visited so that we don't end up in an infinite loop.

# BFS Implementation in Python
from collections import deque

def bfs(graph, start_node):
    visited = {start_node}
    queue = deque([start_node])
    
    while queue:
        vertex = queue.popleft() # Process oldest discovered node
        print(vertex)
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Depth-First Search (DFS): Diving into the Unknown

If BFS is like a ripple in a pond, Depth-First Search is like a person exploring a dark maze. When you reach a junction, you pick one path and follow it as deep as possible until you hit a dead end. Only then do you backtrack to the last junction and try a different path. This "deep-before-wide" strategy is naturally recursive and is the perfect tool for problems involving "possibilities"—such as finding a path through a maze, solving a puzzle, or determining if it's possible to reach one node from another.

DFS is usually implemented using Recursion, which implicitly uses the computer's call stack to remember where to backtrack. You can also implement it iteratively using an explicit Stack (Last-In, First-Out). Like BFS, DFS requires a "Visited" tracker to avoid cycles. Because DFS explores one full branch at a time, it is the standard algorithm for Topological Sorting (ordering tasks based on dependencies) and for detecting cycles in a system.

// Recursive DFS in JavaScript
function dfs(graph, node, visited = new Set()) {
    console.log(node); // Process node
    visited.add(node);
    
    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited); // Dive deep
        }
    }
}

Comparison: When to Use Which?

Choosing between BFS and DFS depends entirely on the question you are trying to answer.

• Shortest Path: BFS is the winner. In an unweighted graph, BFS is guaranteed to find the shortest path from the source to any other node. DFS might find a very long, winding path to a neighbor that was actually right next to the starting point.
• Memory Usage: DFS is often more efficient. In a very wide graph, BFS must store many nodes in its queue at once. In a very deep graph, however, DFS might risk a stack overflow.
• Topological Order: DFS is essential. It can identify the "end" of a dependency chain and work its way backward, which is exactly how compilers order tasks.
• Finding All Paths: DFS is better suited for exploring every possible combination of nodes to reach a target.

Handling Disconnected Graphs

A common mistake when learning traversals is assuming that a single run of BFS or DFS will visit every node in the graph. In the real world, graphs are often "disconnected"—meaning they consist of several isolated "Islands" of nodes. To truly visit every node in a graph, you must loop through all the vertices. For each vertex, if it hasn't been visited yet, you start a new BFS or DFS from that point. This approach allows you to count the number of Connected Components in a network, such as identifying different isolated social groups within a larger population.

// Traversing an entire graph (including disconnected parts)
function traverseFullGraph(graph: ListGraph) {
    const visited = new Set<number>();
    const vertices = Array.from(graph.adjList.keys());
    
    for (const v of vertices) {
        if (!visited.has(v)) {
            // Start a new exploration for each isolated component
            dfs(graph, v, visited); 
        }
    }
}

Advanced Applications: Shortest Paths and Cycles

Once you master basic traversals, you can solve advanced problems with minor modifications. To find the Shortest Path Distance, you can modify BFS to store the distance from the source in each node. To Detect a Cycle in an undirected graph, you can use DFS and check if you ever encounter a visited node that isn't the parent of the current node. These small tweaks transform basic search patterns into powerful diagnostic tools for complex systems.

---

Key Takeaway: Graph traversals are the fundamental algorithms for exploring complex networks. BFS ripples outward to find shortest paths, while DFS dives deep to explore possibilities and dependencies. By combining these patterns with a Visited tracker, you can safely and efficiently navigate any web of data.