BFS vs DFS, step by step.

BFS (breadth-first search) visits a graph level by level, nearest vertices first, keeping the vertices waiting their turn in a queue. DFS (depth-first search) follows one path as deep as it goes, then backtracks, keeping that path on a stack. Both take O(V + E) time with an adjacency list. Use BFS for shortest paths by edges, DFS for backtracking.

Below, both run step by step on the same tree, so you can compare them move by move.

BFS vs DFS: what differs

BFS and DFS on the same tree

Both players start from A on one tree, the BFS topic's default graph, each in its own scene from the app: BFS with its queue, DFS with its stack, the adjacency matrix beside both. BFS visits A, B, E, C, F, D, a level at a time; DFS visits A, B, C, D, E, F, finishing the branch through B before it turns to E. The dotted line joins each vertex to the next one visited. In DFS it follows the edges except from D to E, where DFS has backtracked; in BFS it leaves the edges after A to B.

BFS on a tree

All steps as text
  1. Perform BFS traversal for the given graph, starting from vertex A. A dotted line leads from each visited vertex to the next one visited.
  2. Visit vertex A and enqueue it.
  3. Then dequeue vertex A and check the adjacency matrix to identify its first unvisited neighbor - vertex B. This is the next vertex to visit.
  4. Visit vertex B and enqueue it. Check the adjacency matrix to find unvisited neighbors of vertex A. Vertex E is identified as the next vertex to visit.
  5. Visit vertex E and enqueue it. Since vertex A has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  6. Dequeue vertex B and check the adjacency matrix to identify its unvisited neighbor - vertex C. This is the next vertex to visit.
  7. Visit vertex C and enqueue it. Since vertex B has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  8. Dequeue vertex E and check the adjacency matrix to identify its unvisited neighbor - vertex F. This is the next vertex to visit.
  9. Visit vertex F and enqueue it. Since vertex E has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  10. Dequeue vertex C and check the adjacency matrix to identify its unvisited neighbor - vertex D. This is the next vertex to visit.
  11. Visit vertex D and enqueue it. Since vertex C has no more unvisited neighbors, the next vertex needs to be dequeued from the queue.
  12. Dequeue vertex F. This vertex has no unvisited neighbors, so continue with the next one in the queue.
  13. Dequeue vertex D. Since this vertex has no unvisited neighbors and the queue is empty, all vertices have been visited. The traversal is complete.
  14. BFS visited A, B, E, C, F, D and dequeued them in the same order: six visits, six dequeues and 11 row scans that read 56 cells.
BFS vs DFS — BFS on a tree. Last step: BFS visited A, B, E, C, F, D and dequeued them in the same order: six visits, six dequeues and 11 row scans that read 56 cells.

On the same tree, the stack holds the path from A down to the vertex DFS stands on.

DFS on the same tree

All steps as text
  1. Perform DFS traversal for the given graph, starting from vertex A. A dotted line leads from each visited vertex to the next one visited.
  2. Visit vertex A and push it onto the stack. Using the adjacency matrix, identify an unvisited neighbor — vertex B, the next vertex to visit.
  3. Visit vertex B and push it onto the stack. Using the adjacency matrix, identify an unvisited neighbor — vertex C, the next vertex to visit.
  4. Visit vertex C and push it onto the stack. Using the adjacency matrix, identify an unvisited neighbor — vertex D, the next vertex to visit.
  5. Visit vertex D and push it onto the stack. Since it has no unvisited neighbors, it needs to be popped from the stack.
  6. Pop vertex D. When vertex C returns to the top of the stack and the adjacency matrix shows it has no unvisited neighbors, vertex C needs to be popped from the stack.
  7. Pop vertex C. When vertex B returns to the top of the stack and the adjacency matrix shows it has no unvisited neighbors, vertex B needs to be popped from the stack.
  8. Pop vertex B. Vertex A returns to the top of the stack. The adjacency matrix reveals that vertex A has an unvisited neighbor, vertex E, which will be visited next.
  9. Visit vertex E and push it onto the stack. Using the adjacency matrix, identify an unvisited neighbor — vertex F, the next vertex to visit.
  10. Visit vertex F and push it onto the stack. Since it has no unvisited neighbors, it needs to be popped from the stack.
  11. Pop vertex F. When vertex E returns to the top of the stack and the adjacency matrix shows it has no unvisited neighbors, vertex E needs to be popped from the stack.
  12. Pop vertex E. When vertex A returns to the top of the stack and the adjacency matrix shows it has no unvisited neighbors, vertex A needs to be popped from the stack.
  13. An empty stack indicates that all vertices have been visited and the traversal is complete.
  14. DFS visited A, B, C, D, E, F and popped D, C, B, F, E, A: six visits, six pops and 11 row scans that read 56 cells.
BFS vs DFS — DFS on the same tree. Last step: DFS visited A, B, C, D, E, F and popped D, C, B, F, E, A: six visits, six pops and 11 row scans that read 56 cells.

BFS vs DFS at a glance

Breadth-first search and depth-first search both visit every vertex they can reach from a start vertex, each exactly once. They differ in the order, and the order comes from the container that holds the vertices still to explore.

BFSDFS
OrderLevel by level, nearest firstOne path to its end, then back
ContainerQueue: first in, first outStack or recursion: last in, first out
On the tree aboveA, B, E, C, F, DA, B, C, D, E, F
TimeThe same: O(V + E) with an adjacency list, O(V2) with an adjacency matrix
Extra spaceO(V): the queue, up to two levelsO(V): the stack, one path
Fewest edges to each vertexYes, in an unweighted graphNot guaranteed
Recursive versionNone naturalYes, on the call stack
StrengthFinds what lies near the start firstHolds only the current path
Weak spotA wide graph fills the queueA long path fills the stack
Typical usesShortest paths by edges, levels, bipartite checkBacktracking, cycles, topological order

Queue vs stack: where the next vertex comes from

Both searches find neighbors the same way: findUnvisitedNeighbor(u) scans row u of the adjacency matrix from the left and returns the first unvisited vertex with a 1 in its column. What differs is which vertex they ask next. BFS dequeues the vertex that has waited longest and visits all its unvisited neighbors before it takes the next one, so the search spreads one level at a time. DFS peeks at the vertex pushed last, visits one neighbor and goes on from there at once, so it runs down a path until a dead end, then pops back to the nearest vertex with a neighbor left. In pseudocode, with the app's names for visit and findUnvisitedNeighbor:

bfs(start)
    queue = empty queue
    visit(start)
    queue.enqueue(start)
    while queue is not empty
        u = queue.dequeue()
        v = findUnvisitedNeighbor(u)
        while v is not none
            visit(v)
            queue.enqueue(v)
            v = findUnvisitedNeighbor(u)

dfs(start)
    stack = empty stack
    visit(start)
    stack.push(start)
    while stack is not empty
        u = stack.peek()
        v = findUnvisitedNeighbor(u)
        if v is none
            stack.pop()
        else
            visit(v)
            stack.push(v)

findUnvisitedNeighbor(u)
    for v from 0 to V - 1
        if matrix[u][v] == 1
            if v is not visited
                return v
    return none

Vertices are numbered from 0, and visit marks a vertex as visited. Give DFS's loop a queue in place of the stack, reading the front vertex and dequeuing it when it has no unvisited neighbor left, and it visits in BFS order.

Shortest paths by edges: BFS finds them, DFS does not

In an unweighted graph BFS reaches every vertex by a path with the fewest edges, as it finishes each level before it starts the next. DFS reaches a vertex by whatever path it happens to be on. On a triangle of A, B and C, DFS from A goes to B first and reaches C through B, two edges, while BFS finds C one edge from A. On the players' tree each vertex has a single path from A, so both find the same ones.

With weights neither is enough, as both count edges. Dijkstra's algorithm finds the lowest total weight when no weight is negative, and Bellman-Ford handles negative weights too.

BFS vs DFS time and space complexity

The time is the same. Each vertex is visited once, and the work goes into finding neighbors: O(V + E) with an adjacency list, which holds only real neighbors, and O(V2) with an adjacency matrix, whose rows have V cells each.

The undirected diamond with edges A–B, A–C, B–D and C–D, above its 4 by 4 adjacency matrix, with rows A 0 1 1 0, B 1 0 0 1, C 1 0 0 1 and D 0 1 1 0, and its adjacency list beside the matrix: A: B, C; B: A, D; C: A, D; D: B, C.
The Graph page's diamond as a matrix and as lists. Row A of the matrix has a cell for every vertex; A's list holds only its neighbors, B and C.

Both need O(V) extra space at worst, but they fill it on different graphs. The BFS queue holds at most two neighboring levels, so a wide graph fills it: on a star, one center joined to every other vertex, BFS from the center enqueues all the others at once, while the DFS stack never holds more than two. The DFS stack holds the path from the start, so a long path fills it: on a chain of V vertices, from one end, DFS pushes all of them, while the BFS queue holds one at a time. On the players' tree the queue holds at most two vertices and the stack four.

A recursive DFS keeps that path on the call stack, one nested call per vertex, so on deep graphs an explicit stack is the safe choice.

Note

Python's default recursion limit stops a recursive DFS at about 1,000 nested calls with RecursionError.

When to use BFS and when to use DFS

Use BFS when the answer lies near the start or must take the fewest steps:

  • Fewest moves: a maze or a word ladder, where each move is one edge.
  • Social networks: friends of friends, level by level, up to k hops away.
  • Levels: on a rooted tree BFS is level order traversal.
  • Bipartite check: an edge between two vertices of one level closes an odd cycle, so the graph is not bipartite.
  • Topological sorting by Kahn's algorithm, which keeps a queue of the vertices with no incoming edges left.

Use DFS when you follow whole paths or need the graph's structure:

  • Backtracking: Sudoku, N-Queens and maze solving try one choice to the end before the next.
  • Cycle detection in a directed graph: an edge back to a vertex still on the stack closes a cycle.
  • Topological order: in a directed graph with no cycle, the order in which DFS pops the vertices, reversed.
  • Any path from A to B: the moment DFS reaches B, the stack holds a path to it.
  • Autocomplete: a DFS below a prefix's node in a trie lists every word that starts with it.

For reachability and connected components either works: both visit exactly the vertices that some path joins to the start, in O(V + E).

Common mix-ups

  • DFS finds a shortest path too. Only by chance: on the triangle above it reaches C by two edges where one would do.
  • BFS always needs more memory. Only on wide graphs. On a long chain the DFS stack is the larger one.
  • Any loop with a stack is DFS. Not if it pushes all unvisited neighbors at once and marks them as they are pushed. On a triangle A, B, D with C joined to A only, popping in alphabetical order, it visits A, B, C, D. DFS goes A, B, D, C.
  • Only preorder is depth-first. Preorder, inorder and postorder all walk a tree depth-first, along the same path, and differ only in when a node is processed. DFS's visit order, a vertex as it is first reached, is the preorder.
  • BFS gives shortest paths on any graph. It counts edges, not weights: a road map needs Dijkstra's algorithm.

BFS vs DFS interview questions

Why does BFS find shortest paths in an unweighted graph, and DFS does not?

The queue hands out vertices in the order they were found: every vertex one edge from the start before any two edges away, and so on. The first path by which BFS reaches a vertex is therefore one with the fewest edges. DFS takes whichever path it is on when it first meets a vertex, however long.

Can BFS be written recursively?

Not naturally. Recursion keeps its calls on the call stack, last in, first out, which can stand in for the stack of DFS but not for a first-in, first-out queue.

What is the time complexity of BFS and DFS with an adjacency matrix?

O(V2) for both. Every scan of a row reads up to V cells, and with findUnvisitedNeighbor above a search that reaches every vertex makes 2V − 1 scans: 11 for the six vertices of the players' tree. With an adjacency list, both take O(V + E).

How do you detect a cycle in a directed graph?

With DFS: an edge to a vertex that is still on the stack is a back edge and closes a cycle. With BFS: Kahn's algorithm removes vertices with no incoming edges; if some vertices are never removed, they lie on a cycle or can be reached from one.

Which would you use to find the nearest exit of a maze?

BFS, as it reaches the nearest exit first, by the fewest moves. To learn only whether any exit can be reached, either search works.

One tree here.
Your own graph in the app.

In VisiGrab, BFS and DFS each have a topic with four example graphs, and the Graph Constructor runs either one on a graph you draw.

BFS or DFS, one switch

In the Graph Constructor, place up to 12 vertices, drag edges between them and tap Apply. Flip the DFS / BFS switch and tap the start vertex: each tap on Next visits one vertex and adds it to the traversal order.

Four graphs each

BFS runs on a tree, a ring of six vertices, a graph with two triangles and a fan; DFS on a tree of nine, a graph with a cycle, three chains hanging from A and a ring of eight. Each shows its queue or stack and the adjacency matrix.

Theory for both

The BFS info dialog defines it as closest vertices first, counted in edges. The DFS one has two tabs: graphs and their representations, then dead ends, backtracking and O(V + E) against O(V²).

Python, Java and C++

BFS's loop over a queue and DFS's over a stack, with its recursive version, in all three languages, sharing findUnvisitedNeighbor. Each listing links to its full source on GitHub.

Two quizzes

Four questions on BFS and ten on graphs and DFS, with an explanation for every answer.

More graph algorithms

Topological sort, Dijkstra, Bellman-Ford, Prim, Kruskal and union-find each have a topic of their own.

Breadth or depth,
on one graph.

Download VisiGrab to watch the queue and the stack at work on example graphs, then draw a graph of your own and run both searches on it.

BFS and DFS each have a topic among 30+. See them all