DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
Graph Algorithms algorithms

Graph Algorithms

Graph BFS (Breadth-First Search)

Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.

Worst O(V + E)Space O(V)
Open visualizer

1Detailed explanation

Breadth-first search starts at a vertex, visits all of its neighbours, then all vertices two edges away, and so on. A FIFO queue keeps the discovered-but-unprocessed vertices in exactly that order.

A vertex is marked visited when it is discovered (enqueued), not when it is processed, so it can never be enqueued twice.

Because vertices are discovered in order of distance, dist[v] = dist[parent] + 1 gives the shortest number of edges from the start — BFS is the shortest-path algorithm for unweighted graphs.

2Pseudocode

procedure BFS(G, start)
  visited ← {start}
  dist[start] ← 0
  queue ← [start]
  while queue not empty
    u ← dequeue(queue)
    visit u
    for each neighbor v of u
      if v ∉ visited
        visited ← visited ∪ {v}
        dist[v] ← dist[u] + 1
        enqueue(queue, v)

3Interactive visualization

Graph BFS (Breadth-First Search)interactive Open full visualizer
ABCDEFG

Queue (front → rear)

empty

Traversal order

—
Current vertexIn queueDiscoveredProcessedUnvisited

Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.

1 / 78

4Implementations

Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.

function bfs(graph, start) {
  const visited = new Set([start]);
  const dist = { [start]: 0 };
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dist[neighbor] = dist[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return { order, dist };
}

const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["E", "F"], ["D", "G"], ["F", "G"]];
const graph = {};
for (const [u, v] of edges) {
  (graph[u] ??= []).push(v);
  (graph[v] ??= []).push(u);
}
const { order, dist } = bfs(graph, "A");
console.log("BFS order:", order.join(" -> "));
console.log("Distances:", order.map((v) => v + "=" + dist[v]).join(", "));

5Time and space complexity

Time
Best caseO(V + E)
Average caseO(V + E)
Worst caseO(V + E)
Space
AuxiliaryO(V)
InputO(V + E)
TotalO(V + E)

Time: Every reachable vertex is enqueued and dequeued once (O(V)) and every adjacency list is scanned once; in an undirected graph each edge appears twice → O(E). Total O(V + E).

Space: visited, dist and the queue each hold at most V vertices → O(V) auxiliary space. The adjacency list input itself takes O(V + E).

6Common interview variations

  • Shortest path in an unweighted graph / grid.
  • Number of islands (BFS on a grid).
  • Level order traversal of a tree.
  • Word ladder.
  • Check whether a graph is bipartite.

On this page

  1. 01Detailed explanation
  2. 02Pseudocode
  3. 03Interactive visualization
  4. 04Implementations (JS · Python · Java · Go)
  5. 05Time and space complexity
  6. 06Common interview variations