English
Menu

BFS vs DFS: Visit Order, Shortest Paths and Memory

Both are ways to visit every vertex of a graph or tree by following its edges. Breadth-first search (BFS) spreads out in order of distance: it visits all vertices one edge away from the start, then those two edges away, and so on. Depth-first search (DFS) follows one path as far as it can go, and when it reaches a dead end it backs up and tries another path. BFS is implemented with a queue and DFS with a stack or recursion; on a graph stored as adjacency lists, both visit everything in time proportional to the number of vertices plus the number of edges. BFS is the usual choice for shortest paths in unweighted graphs, and DFS for exhaustively exploring every path or detecting cycles.

AspectBreadth-first search (BFS)Depth-first search (DFS)
Visit orderNearest first (fewest edges from the start), spreading out layer by layerGoes deep along one path, backs up at a dead end and moves on to the next path
Data structure usedQueue (first in, first out)Stack (last in, first out) or recursive calls
Shortest pathsIn an unweighted graph, the number of edges when a vertex is first reached is its shortest distance from the startNot guaranteed: a vertex may be reached first by a roundabout path
Time complexity (V vertices, E edges)O(V + E) with adjacency lists, O(V²) with an adjacency matrixSame as BFS: O(V + E) with adjacency lists, O(V²) with an adjacency matrix
Memory useVertices to visit next are kept in the queue; with many branches, a whole layer of vertices sits in the queue at once, so it grows largeWritten recursively, it only needs the vertices on the current path, so memory grows with the depth of the path; very deep searches can overflow the call stack
Whether a solution is foundAlways found if there are finitely many vertices; even when the search space grows without limit, shallow solutions are found firstAlways found in a finite graph if visited vertices are recorded; when paths can get deeper without limit, it may keep going down one path and never come back
Tree traversal orderLevel order (level by level from the root, left to right)Preorder, inorder and postorder
Typical usesShortest paths in unweighted graphs, the minimum number of moves in a maze, how many hops a network reachesExhaustive search of mazes and puzzles (backtracking), finding connected components and cycles, topological sorting

Figures are typical orders of magnitude and vary by process generation and product.

When to use which

Breadth-first search
When you want the minimum number of steps or the shortest path in an unweighted graph, or want to examine vertices in order of closeness to the start. For shortest paths with weighted edges, use Dijkstra's algorithm.
Depth-first search
When you want to explore every path or combination exhaustively, find connected components or cycles, or perform a topological sort to order tasks. It can be written compactly with recursion.

FAQ

Does BFS find shortest paths when edges have weights?

No, because the path with the fewest edges does not necessarily have the smallest total weight. If the weights are zero or more, use Dijkstra's algorithm. Dijkstra's algorithm replaces the queue with a priority queue that removes the vertex closest to the start first, and can be seen as an extension of BFS to weighted graphs.

Should DFS be written with recursion or an explicit stack?

Recursion is short and easy to read, but in very deep graphs the nested calls can overflow the call stack. Writing it as a loop with your own stack avoids this. Depending on the order in which neighbors are pushed onto the stack, however, the visit order may differ from the recursive version.

What happens if visited vertices are not recorded?

In a graph with cycles, the same vertices are visited again and again. In BFS the queue grows without limit, and in DFS the search can go around the same cycle forever. In both methods, therefore, visited vertices (or vertices already added to the queue or stack) are marked so they are never added again.

Check your understanding

In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?

  1. ABreadth-first search with a queue
  2. BDepth-first search with a stack
  3. CBreadth-first search with a stack
Show answer and explanation

Answer: A. Breadth-first search with a queue

Breadth-first search visits vertices in order of distance: first those one edge from the start, then those two edges away, and so on. Adding each newly found vertex to the back of a queue and taking vertices from the front preserves this nearest-first order, so the number of edges when a vertex is first reached is the shortest. Depth-first search (using recursion or a stack) goes as far as it can along one path, so it may first reach a vertex by a roundabout route, and shortest distances are not guaranteed. Using a stack instead of a queue turns the traversal into something close to depth-first search.

In an undirected graph, the neighbors of each vertex are A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. A recursive depth-first search starts from vertex A. The neighbors are examined in the order listed, and as soon as an unvisited vertex is found, the search moves to it. In what order are the vertices visited?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Show answer and explanation

Answer: C. A, B, D, E, F, C

From A the search moves to B, then to D, the first unvisited neighbor of B. D's only neighbor, B, is already visited, so it returns to B and moves on to E, then from E to the unvisited F, and from F to its neighbor C. The order is therefore A, B, D, E, F, C. A, B, C, D, E, F is the breadth-first search order, which visits vertices nearest-first. A, B, D, E, C, F turns back from E without going to the unvisited F, so it is not a depth-first order.

Which is an appropriate way to store in memory a sparse graph, one with few edges compared with its number of vertices, such as a road network with about 1 million vertices and 3 million edges?

  1. AAn adjacency matrix: it can check whether two vertices are connected in O(1) and also uses the least memory
  2. BAdjacency lists: memory is proportional to the number of vertices plus the number of edges, and they suit following the edges out of a vertex one by one
  3. CAn adjacency matrix: its memory is proportional only to the number of edges
Show answer and explanation

Answer: B. Adjacency lists: memory is proportional to the number of vertices plus the number of edges, and they suit following the edges out of a vertex one by one

An adjacency matrix uses a V × V table for V vertices, so 1 million vertices need 10¹² entries, about 125 GB even at 1 bit per entry. Adjacency lists store only the neighbors of each vertex, so memory is O(V + E), only a few million entries in this example. An adjacency matrix has the advantage of checking for an edge in O(1) and suits dense graphs or graphs with few vertices. For processing that follows the edges out of each vertex in turn, such as breadth-first search and Dijkstra's algorithm, adjacency lists are more efficient.

  1. In an undirected graph, the edge weights (distances) are S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 and A−T: 6. Which shows the shortest path from S to T found by Dijkstra's algorithm and its length?
  2. The values 50, 30, 70, 20, 40, 60, 80 are inserted in this order into an empty binary search tree. In what order are the nodes visited when the tree is traversed in post-order (left subtree, right subtree, then the node)?

Practice Data Structures and Algorithms questions

Key terms explained

Breadth-first search
A way of searching a graph or tree that visits vertices in order of distance from the start: first those one edge away, then those two edges away, and so on. It is implemented with a queue, and in a graph without edge weights it finds the smallest number of edges from the start to every vertex. It is abbreviated BFS.
Depth-first search
A way of searching a graph or tree that goes as far as possible along one path and backtracks to try another path when it reaches a dead end. It is implemented with recursion or a stack and is used for maze solving, finding connected components and cycles, and topological sorting. It is abbreviated DFS.
Queue
A first-in, first-out (FIFO) data structure in which the element added first is removed first. Adding to the back is called enqueue and removing from the front is called dequeue. Queues are used for waiting lines of work, passing data between tasks and breadth-first search.
Stack
A last-in, first-out (LIFO) data structure in which the element added last is removed first. Adding an element is called push and removing one is called pop. Stacks are used to manage return addresses and local variables in function calls (the call stack), to evaluate expressions in Reverse Polish notation and for depth-first search.
Recursion
A function calling itself as part of its own processing. The problem is split into smaller problems of the same form, and the calls stop at a case that is not split further (the base case). Each call uses stack space, so recursion that is too deep overflows the stack. Tail recursion, where the recursive call is the last thing the function does, can be converted into a loop.
Dijkstra's algorithm
An algorithm that finds the shortest paths from one starting vertex to every vertex in a graph whose edge weights are 0 or greater. It repeatedly finalizes the nearest vertex whose distance is not yet final and updates the distances of its neighbors. It does not work correctly with negative edge weights.
Time complexity (Big-O notation)
A description of how the work (time complexity) or memory (space complexity) an algorithm needs grows with the number of data items n. It is written in Big-O notation, such as O(n), O(n log n) or O(n²), dropping constant factors and lower-order terms.

Related comparisons