Graph Traversal: BFS & DFS

The one new worry: cycles

Walking a tree was carefree because a tree has no loops — recursion naturally bottoms out at the leaves. A graph is different: follow edges and you can circle right back to where you started. If you explore A→B→C→A→B→C… you'll loop forever. So every graph traversal carries one extra piece of bookkeeping the tree never needed: a visited set — a record of which vertices you've already seen, so you visit each at most once.

With that one safeguard in place, both traversals share the same skeleton: start somewhere, mark it visited, and keep expanding to *unvisited* neighbors until you run out. The only thing that differs between the two famous algorithms is the order in which they pull the next vertex to expand — and that single choice gives them wildly different personalities.

Breadth-first search: expanding rings

[[breadth-first-search|Breadth-first search]] (BFS) explores like a ripple in a pond: first the start vertex, then *all* its immediate neighbors, then everything one step past those, and so on — level by level. The tool that produces this order is the [[queue|queue]] from your linear-structures rung: first-in, first-out. You enqueue the start, then repeatedly dequeue a vertex and enqueue its unvisited neighbors. Because the queue hands back vertices in the order they were discovered, nearer vertices always come out before farther ones.

  start=0     BFS visit order, level by level:
   (0)        level 0: 0
   / \        level 1: 1, 2     (neighbors of 0)
 (1) (2)      level 2: 3, 4     (one more step out)
  |    |
 (3)  (4)     0 is found at distance 0, 3 at distance 2.

#include <queue>
#include <vector>
void bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<bool> visited(adj.size(), false);
    std::queue<int> q;
    visited[start] = true;          // mark on discovery, not on visit
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        std::cout << u << ' ';      // process u
        for (int v : adj[u])        // each unvisited neighbor
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
    }
}

That ring-by-ring order is BFS's superpower: in an unweighted graph, the first time BFS reaches a vertex, it has reached it by the *fewest possible edges*. So BFS finds the shortest path (in number of hops) from the start to every other vertex — track each vertex's discoverer and you can reconstruct the route. It's also exactly *level-order* traversal when run on a tree.

Depth-first search: down one path

[[depth-first-search|Depth-first search]] (DFS) has the opposite temperament. Instead of spreading evenly, it commits to one path and follows it as deep as it can go, only backtracking when it hits a dead end. It's how you'd explore a maze keeping one hand on the wall. The natural engine is the call stack of [[dsa-recursion|recursion]] (last-in, first-out) — you recurse into a neighbor, and the runtime remembers where to come back. (You can also do it with an explicit `std::stack`, which is the iterative twin.)

void dfs(const std::vector<std::vector<int>>& adj,
         int u, std::vector<bool>& visited) {
    visited[u] = true;
    std::cout << u << ' ';          // process u
    for (int v : adj[u])            // dive into the first
        if (!visited[v])            // unvisited neighbor,
            dfs(adj, v, visited);   // all the way down, then backtrack
}
// call: std::vector<bool> visited(adj.size(), false);
//       dfs(adj, 0, visited);

Both BFS and DFS share the same cost. Each vertex is processed once and each edge is looked at once, so the total work is O(V + E) — V for the vertices, E for the edges. That linear cost is why traversal is the cheap, dependable foundation that fancier graph algorithms build on top of.

What this unlocks

These two traversals are doorways, not destinations. Once you can systematically visit a graph, a whole catalog of problems opens up — here's a preview of what's just ahead.

1. Connectivity & cycle detection — run a traversal and see what you can reach, or whether you ever loop back.
2. Shortest path — BFS solves it for unweighted graphs; when edges carry weights you'll reach for Dijkstra's algorithm, a weighted cousin built on the same idea of expanding outward.
3. Topological sort — for a directed acyclic graph (like task dependencies), DFS produces a valid order to do everything so that nothing comes before its prerequisite.