Graph Traversal — BFS & DFS

What is a graph?

A graph is a set of vertices (nodes) connected by edges (links). Unlike a tree, a graph can have cycles and any node can connect to any other.

Graphs are everywhere: cities and roads, people and friendships, web pages and links, computers in a network.

Traversing a graph means visiting every reachable node exactly once. There are two classic ways to do it.

Breadth-First Search (BFS) — ripples in water

BFS explores in rings: first the start node, then all its neighbours (distance 1), then all their new neighbours (distance 2), and so on.

It uses a queue (first in, first out):

1. Mark the start node and enqueue it.
2. Dequeue the oldest node u and visit it.
3. For each neighbour v of u that isn’t marked yet: mark it and enqueue it.
4. Repeat until the queue is empty.

Because nodes are processed in the order they were discovered, BFS finds the shortest path in edges from the start to every node. In the 3D model, the “level” tag on each node is exactly that distance.

Analogy: spreading news. You tell all your friends first; then each of them tells their friends; and so on outward.

Depth-First Search (DFS) — exploring a maze

DFS follows one path as far as possible, and only when it hits a dead end does it backtrack to the last place it had a choice.

It uses a stack (last in, first out) — or simply recursion, which uses the call stack:

1. Push the start node.
2. Pop the newest node u. If already visited, skip it. Otherwise visit it.
3. Push all unvisited neighbours of u.
4. Repeat until the stack is empty.

Analogy: exploring a maze by always taking the next corridor until you hit a wall, then walking back to the last junction.

BFS vs DFS — the only real difference

Look at the row of boxes in front of the graph. Both algorithms keep a list of “nodes to visit later”. BFS takes from the front (oldest first), DFS takes from the top (newest first). That one choice produces completely different exploration orders.

Code

from collections import deque

graph = {
    'A': ['B', 'C', 'D'], 'B': ['A', 'E', 'F'], 'C': ['A', 'F', 'G'],
    'D': ['A', 'G', 'H'], 'E': ['B', 'F'],      'F': ['B', 'C', 'E'],
    'G': ['C', 'D', 'H'], 'H': ['D', 'G'],
}

def bfs(start):
    order, seen = [], {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()                 # oldest first
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                seen.add(v)
                queue.append(v)
    return order

def dfs(start):
    order, visited = [], set()
    stack = [start]
    while stack:
        u = stack.pop()                     # newest first
        if u in visited:
            continue
        visited.add(u)
        order.append(u)
        for v in reversed(graph[u]):
            if v not in visited:
                stack.append(v)
    return order

print(bfs('A'))   # ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
print(dfs('A'))   # ['A', 'B', 'E', 'F', 'C', 'G', 'D', 'H']

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> adj;           // adjacency list
vector<bool> visited;

void dfs(int u) {                  // recursive DFS
    visited[u] = true;
    cout << char('A' + u) << " ";
    for (int v : adj[u])
        if (!visited[v]) dfs(v);
}

void bfs(int start) {
    vector<bool> seen(adj.size(), false);
    queue<int> q;
    seen[start] = true;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << char('A' + u) << " ";
        for (int v : adj[u])
            if (!seen[v]) { seen[v] = true; q.push(v); }
    }
}

int main() {
    adj = {{1,2,3}, {0,4,5}, {0,5,6}, {0,6,7}, {1,5}, {1,2,4}, {2,3,7}, {3,6}};
    bfs(0); cout << "\n";          // A B C D E F G H
    visited.assign(adj.size(), false);
    dfs(0); cout << "\n";          // A B E F C G D H
}

Where are BFS and DFS used?

• GPS / games: BFS finds the fewest moves in a grid or maze.
• Social networks: “people you may know” = friends at distance 2 (BFS).
• Web crawlers explore links with BFS.
• Compilers and build tools order tasks with a DFS-based topological sort.
• Detecting cycles and finding connected components with DFS.
• Solving puzzles like Sudoku with DFS + backtracking.

Common mistakes

• Forgetting the visited/marked set — the program loops forever on a cycle.
• In BFS, marking a node when it is dequeued instead of when it is enqueued, which lets the same node enter the queue many times.
• Assuming DFS gives shortest paths. It doesn’t.