DSA Lesson 19 of 33

Breadth First Search

Learn how BFS explores a graph level by level.

Course Progress58%

Theory

Breadth First Search, or BFS, explores a graph level by level. It commonly uses a queue. BFS is useful for finding the shortest path in an unweighted graph and for level-order traversal of trees.

Example

const graph = { A: ["B", "C"], B: ["D"], C: [], D: [] }; const queue = ["A"]; const visited = new Set(); while (queue.length > 0) { const node = queue.shift(); if (visited.has(node)) continue; visited.add(node); for (const next of graph[node]) { queue.push(next); } } console.log([...visited]);

Expected Output

The graph nodes are visited level by level.

Practice

Implement BFS for a small graph.

Interview Questions

  1. What is BFS?
  2. Which data structure does BFS use?
  3. Where is BFS useful?
  4. What is the complexity of BFS?