# BFS vs DFS Graph Traversal: Key Differences and When to Use Each

> Understand BFS vs DFS graph traversal. Learn how BFS finds shortest paths with a queue and DFS explores deeply with recursion for cycle detection and topological sorting.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**BFS explores graphs level-by-level using a queue to guarantee shortest paths in unweighted graphs, while DFS uses recursion to explore branches deeply, making it superior for cycle detection and topological sorting.**

Understanding the **difference between BFS and DFS** is essential for selecting the right graph traversal strategy. Both algorithms are implemented in the `trekhleb/javascript-algorithms` repository with a unified callback-based API, but they differ critically in exploration order, space utilization, and optimal use cases.

## Core Differences in Exploration Order

### BFS: Queue-Based Level-Order Traversal

In [`src/algorithms/graph/breadth-first-search/breadthFirstSearch.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/breadth-first-search/breadthFirstSearch.js), the algorithm uses a `Queue` instance from [`src/data-structures/queue/Queue.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/queue/Queue.js) to manage the frontier. It dequeues a vertex, processes it, then enqueues all unvisited neighbors before moving to the next level. This ensures vertices are visited in **level order**—all nodes at distance *k* from the start are processed before nodes at distance *k+1*.

### DFS: Recursive Depth-First Exploration

The implementation in [`src/algorithms/graph/depth-first-search/depthFirstSearch.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/graph/depth-first-search/depthFirstSearch.js) uses a recursive helper function `depthFirstSearchRecursive`. Instead of a separate queue, it leverages the **call stack** to track vertices, exploring as far as possible along each branch before backtracking. This creates a **pre-order** (`enterVertex`) and **post-order** (`leaveVertex`) view of the graph structure.

## Time and Space Complexity Analysis

Both algorithms run in **O(V + E)** time where *V* is vertices and *E* is edges. However, space consumption differs significantly:

- **BFS**: Requires **O(V)** space for the queue in the worst case, potentially storing an entire frontier level (all vertices at the current distance).
- **DFS**: Requires **O(V)** space for the recursion stack, proportional to the maximum depth of the graph. In skewed trees or deep graphs, this can cause stack overflow, though iterative DFS implementations can mitigate this.

## Use Cases: When to Use BFS vs DFS

### Shortest Path and Level-Order Processing (BFS)

Because BFS visits vertices in increasing order of distance from the start, the first time you reach a target vertex is guaranteed to be via the **shortest path** (in unweighted graphs). Use BFS when you need:
- Shortest-path guarantees without edge weights
- All nodes within *k* hops of a start vertex
- Level-order traversal for hierarchical data

### Cycle Detection and Topological Sorting (DFS)

DFS excels when you need to explore branch completion states. The `leaveVertex` callback fires after all descendants are processed, enabling **topological sorting** via finishing times. Use DFS for:
- Detecting cycles in directed graphs (via back-edge detection in `allowTraversal`)
- Topological sorting of dependency graphs
- Exploring all paths in puzzles or maze solving where depth matters

## Implementation Architecture in JavaScript-Algorithms

Both implementations share an identical `Callbacks` interface:

- `allowTraversal({ currentVertex, nextVertex })`: Controls whether to follow an edge (defaults to a `seen` Set closure preventing revisits)
- `enterVertex({ currentVertex, previousVertex })`: Fires when first reaching a vertex (pre-order for DFS, dequeue for BFS)
- `leaveVertex({ currentVertex, previousVertex })`: Fires when finished processing a vertex and its descendants (post-order, primarily used in DFS)

This modular design accepts any `Graph` instance from [`src/data-structures/graph/Graph.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/data-structures/graph/Graph.js) that implements `getNeighbors()` and `getAllVertices()`, working seamlessly across directed, undirected, weighted, or unweighted graphs.

## Practical Code Examples

### Basic BFS Traversal

```javascript
import Graph from './src/data-structures/graph/Graph';
import GraphVertex from './src/data-structures/graph/GraphVertex';
import breadthFirstSearch from './src/algorithms/graph/breadth-first-search/breadthFirstSearch';

const graph = new Graph(true);
const A = new GraphVertex('A');
const B = new GraphVertex('B');
const C = new GraphVertex('C');

graph.addVertex(A).addVertex(B).addVertex(C);
graph.addEdge(A, B).addEdge(B, C);

breadthFirstSearch(graph, A, {
  enterVertex: ({ currentVertex }) => console.log('Visited', currentVertex.getKey()),
});

```

This visits vertices in level order: `A → B → C`.

### BFS with Custom Edge Filtering

```javascript
breadthFirstSearch(graph, A, {
  allowTraversal: ({ currentVertex, nextVertex }) => {
    // Skip the edge A → B specifically
    return !(currentVertex.getKey() === 'A' && nextVertex.getKey() === 'B');
  },
});

```

As demonstrated in [`breadthFirstSearch.test.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/breadthFirstSearch.test.js), this prevents traversal along specific edges while maintaining the level-order guarantee.

### DFS with Pre and Post-Order Callbacks

```javascript
import depthFirstSearch from './src/algorithms/graph/depth-first-search/depthFirstSearch';

depthFirstSearch(graph, A, {
  enterVertex: ({ currentVertex }) => console.log('Enter', currentVertex.getKey()),
  leaveVertex: ({ currentVertex }) => console.log('Leave', currentVertex.getKey()),
});

```

This logs `Enter` when first visiting a vertex and `Leave` after all descendants are processed, essential for algorithms like topological sort.

### Cycle Detection Pattern

The repository's [`detectDirectedCycle.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/detectDirectedCycle.js) utilizes DFS with a custom `allowTraversal` that tracks vertices currently in the recursion stack. When attempting to visit a neighbor already in the active path (a back-edge), the function returns `false` and reports a cycle—demonstrating DFS's natural fit for this problem class.

## Summary

- **BFS** uses a `Queue` to explore level-by-level, guaranteeing shortest paths in unweighted graphs and consuming memory proportional to the frontier width.
- **DFS** uses recursion (call stack) to explore depth-first, enabling topological sorting and cycle detection via post-order callbacks.
- Both algorithms share **O(V + E)** time complexity and a unified callback interface in `trekhleb/javascript-algorithms`, but differ in **O(V)** space characteristics (queue vs recursion stack).
- Choose **BFS** for shortest-path queries and level-order processing; choose **DFS** for deep exploration, cycle detection, and topological ordering.

## Frequently Asked Questions

### Which is faster, BFS or DFS?

Both algorithms have identical **O(V + E)** time complexity. Performance differences are negligible for asymptotic analysis; choose based on whether you need shortest-path guarantees (BFS) or deep branch exploration (DFS) rather than raw speed.

### Can I use DFS to find the shortest path in an unweighted graph?

No. While DFS will eventually find a path to the target, it does not guarantee the shortest one because it may explore a long branch before discovering a shorter alternative. **BFS** is the correct choice for unweighted shortest-path problems because it explores vertices in order of increasing distance from the start.

### Why does BFS sometimes use more memory than DFS?

BFS stores the entire **frontier** (all vertices at the current distance) in its queue, which can be **O(V)** in dense graphs or wide trees. DFS only stores the current path in the recursion stack, which is **O(V)** in the worst case (deep linear chains) but often less in practice. However, BFS can consume more memory in wide, shallow graphs compared to DFS.

### How do I detect cycles using these algorithms?

Use **DFS** with a custom `allowTraversal` callback that tracks vertices currently in the recursion stack. If you encounter a neighbor already in the active path (a back-edge), a cycle exists. The repository demonstrates this pattern in cycle detection implementations that wrap the base `depthFirstSearch` function.