Algorithms/Graph/Breadth-First Search

Breadth-First Search (BFS)

Traverse graph nodes level-by-level using a FIFO queue. Guarantees the shortest path in unweighted graphs.

GraphTraversalShortest PathQueue (FIFO)O(V+E)

Graph Canvas(7 nodes, 10 edges)

1 / 0

Speed

bfs.js

1function bfs(graph, source, target) {

2 const queue = [source];

3 const visited = new Set([source]);

4 const level = { [source]: 0 };

5 const prev = { [source]: null };

7 while (queue.length > 0) {

8 const current = queue.shift(); // Dequeue FIFO

9 if (current === target) break;

11 for (const neighbor of graph[current]) {

12 if (!visited.has(neighbor)) {

13 visited.add(neighbor);

14 level[neighbor] = level[current] + 1;

15 prev[neighbor] = current;

16 queue.push(neighbor); // Enqueue

17 }

18 }

19 }

21 return { level, prev };

22}

Algorithm Explanation

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores nodes level by level starting from a designated source node.

⚙️ How It Works

Initialize — Enqueue the source node into a First-In-First-Out (FIFO) queue and mark it as visited with discovery level 0.
Dequeue — Remove the front node from the queue.
Explore Neighbors — For each unvisited neighbor of the current node, set its discovery level to level[current] + 1, set its parent pointer, mark it as visited, and push it into the queue.
Repeat — Continue dequeuing and expanding until the queue is empty or the target node is reached.
Reconstruct Path — Trace parent pointers backward from target to source.

🔑 Key Property — Shortest Path in Unweighted Graphs

Because BFS visits all nodes at distance k before any node at distance k + 1, the first time BFS reaches a node, it is guaranteed to have found the shortest path (fewest edges) to that node in an unweighted graph.

💡 Dynamic Graph Extension: You can add new nodes and custom edges to the graph using the + Add Node tool in the visualizer above!

Click nodes to set source/target · Drag nodes to rearrange layout · Use "+ Add Node" to extend graph topology