Graph Traversal

Breadth-First Search

What is Breadth-First Search?

Breadth-First Search explores a graph outward from a starting vertex one "ring" of distance at a time: first the start vertex itself, then all of its direct neighbors, then all of their unvisited neighbors, and so on. The result is that every vertex gets visited in order of its distance (in number of edges) from the start — nothing two hops away is visited before everything one hop away.

How Does It Work?

That ordering comes entirely from using a queue (first-in, first-out) instead of a stack. The start vertex is enqueued first. Then, repeatedly: dequeue a vertex, mark it visited, and enqueue any of its neighbors that haven't been visited yet. Because a queue preserves arrival order, every vertex discovered while processing distance-d vertices gets enqueued *after* all the other distance-d vertices already in the queue — which guarantees they'll all be dequeued (and their own neighbors discovered) before any distance-(d+1) vertex is dequeued.

A visited set is essential alongside the queue: without one, a vertex reachable from multiple directions would be enqueued (and processed) more than once, and a graph with a cycle could loop forever. Marking a vertex visited *at the moment it's enqueued* — not when it's dequeued — is what prevents the same vertex from being added to the queue twice while it's still waiting its turn.

BFS from A visits every vertex in order of distance — amber, then blue, then emerald

Algorithm Steps

Enqueue the start vertex and mark it visited
While the queue isn't empty, repeat:
- Dequeue a vertex and process it (this is the visit order)
- For each of its neighbors, if not already visited: mark it visited and enqueue it
Stop when the queue is empty — every vertex reachable from the start has been visited

Time Complexity

Time Complexity: O(V + E) — every vertex is dequeued once and every edge is examined once across the whole run.
Space Complexity: O(V) — for the queue and the visited set in the worst case.

Time Complexity Analysis

BFS is the standard choice whenever "shortest path in terms of number of edges" is what's needed — it's how the "N degrees of separation" between two people in a social graph is found, how the fewest moves to solve a sliding puzzle is computed, and how the shortest route in an unweighted road network is found. For weighted graphs where edges have different costs, Dijkstra's algorithm generalizes this same expanding-frontier idea.

Daily DSA Challenge by Scale Engineer

Watch Breadth-First Search explore a graph one ring of distance at a time

Directed graph

Build a graph, pick a start vertex, and run BFS

Graph

Add a vertex to begin

UnvisitedVisitedCurrently dequeuedEdge being explored

Test Your Knowledge before moving forward!

Breadth-First Search Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Breadth-First Search Implementation

// A queue (FIFO) is what makes this "breadth-first": every same-distance
// vertex is dequeued before any farther vertex is even discovered.
function bfs(adjList, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const current = queue.shift();
    order.push(current);

    for (const neighbor of adjList[current] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // mark visited when enqueued, not when dequeued
        queue.push(neighbor);
      }
    }
  }

  return order;
}

// Usage example
const adjList = { A: ["B", "C"], B: ["A", "D"], C: ["A"], D: ["B"] };
bfs(adjList, "A"); // ["A", "B", "C", "D"]

Done With the Learning

Mark Breadth-First Search as done and view it on your dashboard

Explore Other Topics

Depth-First Search

Dijkstra's Algorithm

Adjacency List

Adjacency Matrix

Binary Search

Structure & Properties