BFS vs DFS: Graph Traversal Traced Step by Step

The graph, and the conventions we are fixing

Seven vertices labelled 0–6, undirected, unweighted, connected. The eight edges are:

0–1, 0–2, 1–3, 1–4, 2–4, 3–5, 4–5, 5–6

Drawn roughly: 0 sits at the top with children 1 and 2; 1 joins 3 and 4; 2 also joins 4; 3 and 4 both join 5; 5 hangs off to 6.

As adjacency lists, each list sorted ascending:

Conventions used everywhere on this page (state these in any answer you write, then no marker can call your order wrong):

• Start vertex is 0 unless stated otherwise.
• Neighbours are examined in ascending label order.
• BFS marks a vertex visited when it is enqueued.
• Recursive DFS marks a vertex visited when the call on it begins.
• Iterative DFS marks a vertex visited when it is popped, and pushes neighbours in descending order so that the smallest label ends up on top of the stack. That combination is what makes an iterative DFS agree with the recursive one.

Note the graph has cycles (1–3–5–4–1 for one), so "already visited" checks genuinely matter — this is not a tree in disguise.

BFS traced, one step per dequeue

BFS uses a FIFO queue. Invariant: the queue always holds vertices in non-decreasing order of distance from the source, and it never contains more than two distinct distance layers at once. That invariant is the whole reason BFS finds shortest hop counts.

Starting state: visited = {0}, queue = [0], output empty. Each row below is one loop iteration: dequeue the front, print it, enqueue its unvisited neighbours (marking them as you enqueue).

BFS order: 0 1 2 3 4 5 6.

The distances and BFS-tree parents fall out for free:

Following parents backwards from 6 gives the shortest path 0 → 1 → 3 → 5 → 6, four hops. Watch step 3 and step 5: those are the cycle edges being rejected. Vertex 2 wants to visit 4, but 1 already claimed it one step earlier, so 4 keeps parent 1. Nothing about 2 being "closer" changes — both are at distance 1, and BFS breaks the tie by neighbour order.

DFS traced, recursively

Recursive DFS needs no visible stack — the call stack is the stack. Trace it by indentation; the output is the pre-order of the DFS tree.

visit 0            out: 0
  0's nbrs 1,2 → try 1
  visit 1          out: 0 1
    1's nbrs 0(✔),3,4 → try 3
    visit 3        out: 0 1 3
      3's nbrs 1(✔),5 → try 5
      visit 5      out: 0 1 3 5
        5's nbrs 3(✔),4,6 → try 4
        visit 4    out: 0 1 3 5 4
          4's nbrs 1(✔),2,5(✔) → try 2
          visit 2  out: 0 1 3 5 4 2
            2's nbrs 0(✔),4(✔) → return
          return to 4 → nothing left → return
        back in 5 → try 6
        visit 6    out: 0 1 3 5 4 2 6
          6's nbrs 5(✔) → return
      return to 3, to 1 (4 already ✔), to 0 (2 already ✔) → done

DFS order: 0 1 3 5 4 2 6.

Compare with BFS: 0 1 2 3 4 5 6. Both are valid, both visit all 7 vertices, and only the shape of the frontier differs. BFS fans out; DFS commits to one branch and only backtracks when it dead-ends.

The DFS tree here has edges 0–1, 1–3, 3–5, 5–4, 4–2, 5–6 (6 = V−1 tree edges). The two edges left over, 0–2 and 1–4, are back edges — each one closes a cycle with the tree path between its endpoints. That is the entire basis of DFS cycle detection: an undirected graph has a cycle if and only if a DFS finds an edge to an already-visited vertex that is not the edge it just came in on.

DFS traced with an explicit stack

Same traversal, LIFO stack instead of recursion. Push neighbours in descending order so the smallest label sits on top and gets popped first. Mark visited on pop, and skip anything already visited when it comes off.

Order: 0 1 3 5 4 2 6 — identical to the recursive version.

Two things to notice, because they are exactly what a written trace is testing:

• Duplicates are normal. At step 4 the stack holds 4 twice. That is not a bug; it is why the pop-time if (visited[u]) continue; guard exists. Steps 8 and 9 are pure clean-up of those stale entries. A stack in a mark-on-pop DFS can hold up to O(E) entries.
• Push descending, pop ascending. If you push in ascending order instead, the largest neighbour ends up on top and you get 0 2 4 5 6 3 1 — a perfectly legal DFS of the same graph, just a different one. If a question does not fix the push order, say which one you used.

The ambiguity that changes the answer: mark on push vs mark on pop

This is the single most common source of two students getting two different "correct" answers.

Run the exact same iterative DFS as above — same graph, same start, same descending push order — and change one thing only: mark a vertex visited the moment you push it rather than when you pop it.

Order: 0 1 3 5 6 4 2 versus 0 1 3 5 4 2 6 for mark-on-pop. They diverge from step 5 onwards.

Why? At step 4 the mark-on-pop version pushes 4 a second time, on top of the stack, so 4 is explored immediately as a child of 5 — which is what recursion does. The mark-on-push version refuses to re-push 4 because it was already marked when 1 pushed it, so 4 stays buried in the stack and only surfaces after the 5 branch is exhausted. The mark-on-push variant is not a depth-first order in general; it is a legitimate traversal, it terminates, it visits everything reachable, but it does not match the recursive definition and it will not give you correct DFS tree/back-edge classification.

The rules to memorise:

BFS with mark-on-dequeue still prints the same order here (FIFO preserves first-arrival order) — but it has a nastier side effect. If you also assign dist[v] = dist[u] + 1 at push time without checking visited[v], distances get overwritten by later, larger values. On this graph that buggy version reports distances 2 3 3 4 4 5 4 from vertex 0, including the absurd dist[0] = 2. Mark on enqueue and the problem cannot arise.

The C++ implementation

One graph class, BFS with distances and parents, path reconstruction, recursive DFS, iterative DFS, and cycle detection. This compiles clean under g++ -std=c++17 -Wall -Wextra and produces exactly the orders traced above.

Design notes worth copying:

• std::vector<std::vector<int>> adjacency list, one inner vector per vertex. addEdge is called once per undirected edge and pushes both directions.
• std::vector<char> for visited, not std::vector<bool> — the bool specialisation is a bit-packed proxy type, which is fine here but bites you the moment you want a reference or a pointer to an element.
• dist initialised to -1 doubles as "unreachable", so one array answers both "can I get there?" and "how far?".
• neighbours() returns a const&; taking it by value would silently turn an O(V+E) traversal into an O(V+E) traversal with a heap allocation per vertex.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

class Graph {
public:
    explicit Graph(int n) : adj_(static_cast<std::size_t>(n)) {}

    // Undirected edge: call once per edge, it wires up both directions.
    void addEdge(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }

    const std::vector<int>& neighbours(int u) const { return adj_[u]; }
    int size() const { return static_cast<int>(adj_.size()); }

    // Fix the neighbour-ordering convention once, up front.
    void sortAdjacency() {
        for (auto& row : adj_) std::sort(row.begin(), row.end());
    }

private:
    std::vector<std::vector<int>> adj_;
};

struct BfsResult {
    std::vector<int> order;   // visit order
    std::vector<int> dist;    // hops from source, -1 = unreachable
    std::vector<int> parent;  // BFS tree parent, -1 = none
};

BfsResult bfs(const Graph& g, int src) {
    const int n = g.size();
    BfsResult r{{}, std::vector<int>(n, -1), std::vector<int>(n, -1)};
    std::vector<char> visited(n, 0);
    std::queue<int> q;

    visited[src] = 1;          // mark on ENQUEUE
    r.dist[src] = 0;
    q.push(src);

    while (!q.empty()) {
        int u = q.front();
        q.pop();               // std::queue::pop() returns void - read front() first
        r.order.push_back(u);

        for (int v : g.neighbours(u)) {
            if (!visited[v]) {
                visited[v] = 1;
                r.dist[v]   = r.dist[u] + 1;
                r.parent[v] = u;
                q.push(v);
            }
        }
    }
    return r;
}

// Shortest path src -> dst, empty if unreachable.
std::vector<int> pathTo(const BfsResult& r, int dst) {
    std::vector<int> path;
    if (r.dist[dst] < 0) return path;
    for (int cur = dst; cur != -1; cur = r.parent[cur]) path.push_back(cur);
    std::reverse(path.begin(), path.end());
    return path;
}

void dfsRecursive(const Graph& g, int u,
                  std::vector<char>& visited, std::vector<int>& order) {
    visited[u] = 1;            // mark on ENTRY
    order.push_back(u);
    for (int v : g.neighbours(u))
        if (!visited[v]) dfsRecursive(g, v, visited, order);
}

// Iterative DFS that reproduces the recursive order exactly:
// push neighbours DESCENDING, mark visited ON POP.
std::vector<int> dfsIterative(const Graph& g, int src) {
    std::vector<char> visited(static_cast<std::size_t>(g.size()), 0);
    std::vector<int> order;
    std::stack<int> st;
    st.push(src);

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (visited[u]) continue;      // stale duplicate - discard
        visited[u] = 1;
        order.push_back(u);

        const std::vector<int>& nb = g.neighbours(u);
        for (auto it = nb.rbegin(); it != nb.rend(); ++it)
            if (!visited[*it]) st.push(*it);
    }
    return order;
}

// Undirected cycle detection: any edge to a visited vertex that is not
// the edge we arrived on closes a cycle.
bool hasCycleFrom(const Graph& g, int u, int parent, std::vector<char>& visited) {
    visited[u] = 1;
    for (int v : g.neighbours(u)) {
        if (!visited[v]) {
            if (hasCycleFrom(g, v, u, visited)) return true;
        } else if (v != parent) {
            return true;
        }
    }
    return false;
}

// Works on disconnected graphs too: restart from every unvisited vertex.
int countComponents(const Graph& g) {
    std::vector<char> visited(static_cast<std::size_t>(g.size()), 0);
    std::vector<int> scratch;
    int components = 0;
    for (int s = 0; s < g.size(); ++s) {
        if (!visited[s]) { ++components; dfsRecursive(g, s, visited, scratch); }
    }
    return components;
}

int main() {
    Graph g(7);
    g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4);
    g.addEdge(2, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(5, 6);
    g.sortAdjacency();

    BfsResult b = bfs(g, 0);
    std::cout << "BFS  :"; for (int x : b.order) std::cout << ' ' << x;
    std::cout << "\ndist :"; for (int d : b.dist)  std::cout << ' ' << d;
    std::cout << "\n0->6 :"; for (int x : pathTo(b, 6)) std::cout << ' ' << x;

    std::vector<char> visited(7, 0);
    std::vector<int> order;
    dfsRecursive(g, 0, visited, order);
    std::cout << "\nDFSr :"; for (int x : order) std::cout << ' ' << x;
    std::cout << "\nDFSi :"; for (int x : dfsIterative(g, 0)) std::cout << ' ' << x;

    std::vector<char> cv(7, 0);
    std::cout << "\ncycle: " << (hasCycleFrom(g, 0, -1, cv) ? "yes" : "no")
              << "\ncomps: " << countComponents(g) << '\n';
}

/* Output:
BFS  : 0 1 2 3 4 5 6
dist : 0 1 1 2 2 3 4
0->6 : 0 1 3 5 6
DFSr : 0 1 3 5 4 2 6
DFSi : 0 1 3 5 4 2 6
cycle: yes
comps: 1
*/

Why both are O(V + E), and what changes it

Count the work, do not hand-wave it.

Per-vertex work. Every vertex is pushed into the container at most once (mark-on-push) or visited at most once (mark-on-pop, where the extra stale entries are still bounded by the number of pushes). Popping, marking, and printing are O(1) each. Total: O(V).

Per-edge work. When vertex u is visited, its adjacency list is scanned exactly once — that is deg(u) iterations. Summing over all vertices:

Σ deg(u) = 2E for an undirected graph, = E for a directed one.

So the neighbour scanning across the whole run is O(E), not O(V·E). Each edge is examined twice in an undirected graph, once from each endpoint. Total: O(V + E).

On our graph: 7 vertices, 8 edges, 16 adjacency-list entries examined in total. Both traversals did exactly that amount of work.

Why the V + matters. In a sparse graph E can be as small as 0, and you still have to touch every vertex to know it is isolated. In a dense graph E ≈ V², so O(V+E) degrades to O(V²) — that is the graph's fault, not the algorithm's.

Individual operations:

Space. visited, dist, parent are O(V) each. BFS queue with mark-on-enqueue is O(V); DFS stack with mark-on-pop is O(E) worst case; recursive DFS uses O(V) call-stack frames — which is a real crash risk on a 10⁵-vertex path graph, since each frame is far heavier than one integer.

Adjacency matrix instead of lists. The algorithms are unchanged, but finding the neighbours of u becomes a scan of a whole row: V steps regardless of the actual degree. Total becomes O(V²). On a sparse graph that is strictly worse; on a dense graph it is the same order and the matrix wins on constant factors and O(1) edge lookup. Choose the representation from the density, then quote the matching complexity — quoting O(V+E) for a matrix implementation is simply wrong.

Which one to reach for

Use BFS when the answer depends on distance measured in hops.

• Shortest path in an unweighted graph — the first time BFS reaches a vertex is via a minimum-hop path, guaranteed by the layer invariant. (With weights this collapses; you need Dijkstra.)
• "All vertices within k steps", level-order output, minimum number of moves in a puzzle state graph.
• Testing bipartiteness by 2-colouring layers.
• Finding a nearest match when the target is likely to be shallow — BFS finds it without descending a deep useless branch.

Use DFS when the answer depends on structure rather than distance.

• Cycle detection, and classifying tree/back edges.
• Connected components (BFS works equally well, but DFS is three lines recursively).
• Topological sort and strongly connected components on directed graphs — these are defined in terms of DFS finish times, BFS cannot substitute.
• Path existence, maze solving, backtracking search where you want to commit to one branch and undo.
• Anything needing "what happened below this vertex", because recursion gives you a natural post-order hook on the way back up.

Practical differences that decide it in real code: BFS memory is proportional to the widest layer, which in a broad shallow graph can be enormous; DFS memory is proportional to the longest path, which in a deep chain overflows the call stack. Neither is uniformly cheaper. And a shortest-path question answered with DFS is not slightly wrong — it is wrong, because the first path DFS finds is essentially arbitrary.

Mistakes people actually make

1. Marking visited at the wrong moment in BFS. Enqueueing without marking means a vertex enters the queue once per incoming edge. The order usually survives, but the queue swells to O(E) and any dist/parent you assign at push time gets overwritten by a longer path later. On the graph above this buggy variant reports dist[0] = 2. Mark on enqueue.

2. Forgetting the guard after pop in a mark-on-pop DFS. Without if (visited[u]) continue; you re-visit and re-push, and on a cyclic graph you loop forever. The duplicates on the stack are expected — the guard is what makes them harmless.

3. Adding an undirected edge only once. adj[u].push_back(v); without the mirror gives you a directed graph you did not intend. Symptom: half the graph mysteriously unreachable. Conversely, calling addEdge(u,v) and addEdge(v,u) inserts each direction twice — harmless for correctness, but it doubles the scanning work and breaks any edge counting.

4. Off-by-one in a hand-rolled circular queue. With only head and tail, head == tail means both empty and full — indistinguishable. Two fixes: keep an explicit count, or waste one slot and call it full when (tail + 1) % cap == head. The count version below is easier to get right, and it keeps push after a wrap-around from silently overwriting the front element. A BFS on top of an overwriting queue drops vertices and returns a short, plausible-looking, wrong order.

5. Dangling references and iterator invalidation. const std::vector<int>& nb = g.neighbours(u); is fine only while nothing mutates the graph. If any code inside the loop calls addEdge, the inner vector may reallocate and nb, plus any range-for iterators over it, dangle — undefined behaviour that often "works" in a debug build and corrupts memory in release. Same trap with auto& row = adj[u]; adj.push_back(...); — growing the outer vector moves every inner one. If you must mutate while traversing, index by position (adj[u][i]) and re-check adj[u].size() each iteration, or collect the changes and apply them after.

6. Sizing the adjacency list for 1-indexed vertices. Problem statements often number vertices 1..n; Graph g(n) then makes adj[n] out of bounds. Allocate n + 1 and ignore index 0, or convert to 0-indexed at input. std::vector::operator[] will not tell you — use .at() while debugging.

7. Reusing a stale visited array. Running several queries on the same graph without clearing visited makes every run after the first return almost nothing. std::fill(visited.begin(), visited.end(), 0); between runs, or allocate fresh — and note that visited.clear() empties the vector rather than zeroing it, which then makes every index out of bounds.

8. Not restarting on disconnected graphs. A single BFS/DFS call only covers the source's component. If the question says "traverse the graph", wrap it in for (int s = 0; s < n; ++s) if (!visited[s]) traverse(s);.

9. std::queue::pop() returns void. int u = q.pop(); does not compile; q.pop(); use(q.front()); compiles and reads the wrong element. Always int u = q.front(); q.pop();.

10. Skipping the parent by label in cycle detection. else if (v != parent) return true; is correct for simple graphs, but if the graph can have two parallel edges between u and its parent, the second one is a genuine 2-cycle that this test silently ignores. Track the edge index rather than the parent label if parallel edges are possible. A self-loop u–u, on the other hand, is caught correctly (v == u != parent).

11. Quoting O(V+E) for an adjacency-matrix implementation. It is O(V²). The complexity belongs to the pair of algorithm and representation.

// A circular queue that cannot silently lose elements.
// The explicit count removes the empty/full ambiguity entirely.
#include <cstddef>
#include <vector>

class CircularQueue {
public:
    explicit CircularQueue(int capacity)
        : buf_(static_cast<std::size_t>(capacity)), head_(0), count_(0) {}

    bool empty() const { return count_ == 0; }
    bool full()  const { return count_ == static_cast<int>(buf_.size()); }
    int  size()  const { return count_; }

    // Returns false instead of overwriting the front on overflow.
    bool push(int x) {
        if (full()) return false;
        int tail = (head_ + count_) % static_cast<int>(buf_.size());
        buf_[static_cast<std::size_t>(tail)] = x;
        ++count_;
        return true;
    }

    bool pop(int& out) {
        if (empty()) return false;
        out = buf_[static_cast<std::size_t>(head_)];
        head_ = (head_ + 1) % static_cast<int>(buf_.size());
        --count_;
        return true;
    }

private:
    std::vector<int> buf_;
    int head_;   // index of the front element
    int count_;  // number of live elements; head_ + count_ (mod cap) is the tail
};

// Sized for BFS with mark-on-enqueue, a capacity of V is always enough,
// because every vertex is enqueued at most once.
// With mark-on-dequeue it is NOT enough - you would need E.

Exercises with solutions

Work through each question before opening the solution below it.

visit 2      out: 2      nbrs 0,4 → 0
  visit 0    out: 2 0    nbrs 1,2(✔) → 1
    visit 1  out: 2 0 1  nbrs 0(✔),3,4 → 3
      visit 3      out: 2 0 1 3      nbrs 1(✔),5 → 5
        visit 5    out: 2 0 1 3 5    nbrs 3(✔),4,6 → 4
          visit 4  out: 2 0 1 3 5 4  nbrs 1(✔),2(✔),5(✔) → return
        back in 5 → 6
          visit 6  out: 2 0 1 3 5 4 6  nbrs 5(✔) → return
      unwind: 3 done, 1's remaining nbr 4 is ✔, 0's remaining nbr 2 is ✔, 2's remaining nbr 4 is ✔

std::vector<int> bfsDist(const Graph& g, int src) {
    const int n = g.size();
    std::vector<int> dist(n, -1);
    std::vector<char> visited(n, 0);
    std::queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for (int v : g.neighbours(u)) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    return dist;
}

for (int v : g.neighbours(u)) {
    if (!visited[v]) {          // guard
        visited[v] = 1;         // mark on ENQUEUE, not on dequeue
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}

Related pages