Demystifying Graph Traversals: A Visual Guide to BFS and DFS with Real-World Analogies

Whether you are looking at a map of flight connections, scrolling through recommendations in a social network, or writing a chess engine, you are working with Graphs.

A Graph is one of the most powerful and flexible data structures in Computer Science, used to represent networks of items. But to make sense of these networks, we need ways to search and explore them. This is where Graph Traversals come in.

The two fundamental algorithms for traversing a graph are Breadth-First Search (BFS) and Depth-First Search (DFS).

Here at Curious Folk, we believe in interactive visual learning. In this visual guide, we’ll explore what graphs are, break down how BFS and DFS work using real-world analogies, trace their execution step-by-step, and write clean code implementations in Python and JavaScript.

What is a Graph?

At its core, a Graph is a collection of two elements:

• Vertices (or Nodes): The objects/points in the network (e.g., people, cities, web pages).
• Edges: The links between those nodes (e.g., friendships, flights, hyperlinks).

     ( A ) ------------ ( B )
       |                  |
       |                  |
     ( C ) ------------ ( D )
       \                  /
        \                /
              ( E )

Graphs can be Directed (one-way relationships, like following someone on Twitter) or Undirected (mutual relationships, like Facebook friendships).

1. Breadth-First Search (BFS): The Layer-by-Layer Ripple

Imagine throwing a stone into a still pond. A small wave forms at the impact point and ripples outward in expanding concentric circles, touching everything in the first layer, then the second layer, and so on.

This is Breadth-First Search (BFS). It starts at a source node and explores all its immediate neighbors first, before moving to the neighbors’ neighbors.

The Real-World Analogy: Social Networks (Degrees of Separation)

If you start at yourself (Node 0) and want to find a plumber:

• First, you ask your direct friends (1st degree of separation).
• If none of them are plumbers, you ask your friends’ friends (2nd degree of separation).
• You keep searching wider and wider, level-by-level.

How BFS Works Under the Hood

To explore level-by-level, BFS must remember which nodes it has seen but hasn’t fully explored yet. It does this using a Queue (First In, First Out - FIFO):

1. Add the starting node to the Queue and mark it as Visited.
2. Loop while the Queue is not empty:
   • Remove (Dequeue) the node at the front of the queue.
   • For each unvisited neighbor of this node:
     • Mark it as Visited.
     • Add (Enqueue) it to the back of the queue.

2. Depth-First Search (DFS): The Maze Explorer

Imagine you are trapped inside an ancient, branching maze. To escape, you decide to explore a path as far as it goes.

• If you hit a dead end, you backtrack to the last fork in the road and try the next path.
• To prevent going in circles, you leave a trail of breadcrumbs (visited nodes) behind you.

This is Depth-First Search (DFS). It goes as deep as possible down a path before backtracking.

How DFS Works Under the Hood

DFS needs to keep track of the path it is currently exploring so it can backtrack when it hits a dead end. It does this using a Stack (Last In, First Out - LIFO) or by using Recursion (which uses the CPU’s call stack).

1. Start at a node, mark it as Visited, and push it to the Stack (or call the function recursively).
2. For each unvisited neighbor:
   • Recursively call DFS on that neighbor.
3. If a node has no unvisited neighbors, the function returns (backtracks) to the caller.

Step-by-Step Visual Trace

Let’s trace both algorithms on this simple graph starting from node A:

        ( A )
       /     \
     ( B )   ( C )
      |       |
     ( D )   ( E )

Trace 1: Breadth-First Search (BFS)

BFS Traversal Order: A -> B -> C -> D -> E

Trace 2: Depth-First Search (DFS)

Using Recursion (Call Stack):

DFS Traversal Order: A -> B -> D -> C -> E

Code Implementations

Let’s look at code implementations in JavaScript and Python. We’ll represent the graph using an Adjacency List (a dictionary/hash map where keys are nodes and values are arrays of neighbor nodes).

const graph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': [],
  'E': []
};

1. JavaScript Implementation

// Breadth-First Search (BFS)
function bfs(graph, startNode) {
    const queue = [startNode];
    const visited = new Set([startNode]);
    const result = [];
    
    while (queue.length > 0) {
        const current = queue.shift(); // Remove from front
        result.push(current);
        
        for (const neighbor of graph[current]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor); // Add to back
            }
        }
    }
    return result;
}

// Depth-First Search (DFS) - Recursive
function dfs(graph, startNode, visited = new Set(), result = []) {
    visited.add(startNode);
    result.push(startNode);
    
    for (const neighbor of graph[startNode]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited, result);
        }
    }
    return result;
}

// Execute:
console.log("BFS order:", bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E']
console.log("DFS order:", dfs(graph, 'A')); // ['A', 'B', 'D', 'C', 'E']

2. Python Implementation

from collections import deque

# Breadth-First Search (BFS)
def bfs(graph, start_node):
    queue = deque([start_node])
    visited = {start_node}
    result = []
    
    while queue:
        current = queue.popleft() # O(1) dequeue operation
        result.append(current)
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

# Depth-First Search (DFS) - Recursive
def dfs(graph, current_node, visited=None, result=None):
    if visited is None:
        visited = set()
    if result is None:
        result = []
        
    visited.add(current_node)
    result.append(current_node)
    
    for neighbor in graph[current_node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)
            
    return result

# Graph Adjacency List:
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E'],
    'D': [],
    'E': []
}

print("BFS Order:", bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E']
print("DFS Order:", dfs(graph, 'A'))  # ['A', 'B', 'D', 'C', 'E']

Comparison: BFS vs. DFS

By mastering these two approaches, you gain the vocabulary and templates to solve complex pathfinding, sorting, and analytical problems across millions of connected nodes. Happy traversing! 🚀