Graph Traversal Algorithms Visualized

Graphs are a powerful way to model relationships. They appear everywhere in computer science: social networks, road maps, dependency graphs, build systems, recommendation engines, and scheduling problems.

Graph traversal is the process of visiting nodes in a graph in a systematic way. Unlike arrays or trees, graphs do not have a natural order. Traversal algorithms define how and when nodes are visited.

Two fundamental traversal strategies dominate graph algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). While they both visit every reachable node, they do so in very different orders, leading to different guarantees and use cases.

Why Graph Traversal Matters

Traversal algorithms form the backbone of many higher-level algorithms. Understanding their mechanics is essential for debugging real-world systems and reasoning about correctness and performance.

Core Graph Concepts

• Node (Vertex): a unit in the graph representing an entity
• Edge: a connection between two nodes
• Directed graph: edges have direction
• Undirected graph: edges have no direction
• Adjacency list: a common way to store graphs efficiently
• Visited set: prevents revisiting nodes and infinite loops

Breadth-First Search (BFS)

Breadth-First Search explores a graph level by level. It visits all neighbors of a node before moving deeper into the graph.

How it works:

1. Start from a chosen node
2. Mark it as visited
3. Add it to a queue
4. Repeatedly dequeue a node and visit its unvisited neighbors

Depth-First Search (DFS)

Depth-First Search explores as far as possible along one path before backtracking. It prioritizes depth over breadth.

How it works:

1. Start from a chosen node
2. Visit an unvisited neighbor
3. Continue recursively until no options remain
4. Backtrack and explore other paths

DFS can be implemented recursively (using the call stack) or iteratively (using an explicit stack).

BFS vs DFS Comparison

Code Examples

Breadth-First Search

#include <vector>
#include <queue>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
  std::vector<bool> visited(graph.size(), false);
  std::queue<int> q;

  visited[start] = true;
  q.push(start);

  while (!q.empty()) {
    int node = q.front();
    q.pop();

    for (int neighbor : graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        q.push(neighbor);
      }
    }
  }
}
// This implementation uses an adjacency list and a queue to ensure 
// nodes are visited in increasing distance order.

Depth-First Search (Iterative)

#include <vector>
#include <stack>

void dfs(int start, const std::vector<std::vector<int>>& graph) {
  std::vector<bool> visited(graph.size(), false);
  std::stack<int> s;

  s.push(start);

  while (!s.empty()) {
    int node = s.top();
    s.pop();

    if (visited[node]) continue;
    visited[node] = true;

    for (int neighbor : graph[node]) {
      if (!visited[neighbor]) {
        s.push(neighbor);
      }
    }
  }
}
// Iterative DFS avoids call stack overflow for deep graphs.

Common Pitfalls

Summary

Graph traversal algorithms define how we explore relationships. BFS and DFS form the foundation for many advanced graph algorithms and appear constantly in real-world systems. Understanding how they behave visually helps build intuition that scales far beyond interview problems.

Try It Yourself

Use the interactive visualizer below to compare BFS and DFS. Watch how the queue vs stack affects traversal order, and toggle directed mode to see how edge direction impacts reachability!