Breadth-First Search Visualizer
Graph Traversal BFS Foundation

Breadth-First Search Visualizer

Explore BFS with a queue data structure and level-by-level exploration. Watch how the algorithm expands outward from the start node, visiting all neighbors before moving deeper. Step through the execution to see the complete picture.

Theory

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes layer by layer, visiting all neighbors before moving to the next level. It uses a queue — a FIFO (First-In-First-Out) data structure — to maintain the frontier of unexplored nodes. BFS is fundamental for finding shortest paths, level-order traversals, and connectivity analysis in unweighted graphs.

  • Strategy: Explore all neighbors before their children — uses FIFO (queue) ordering to guarantee level-order expansion
  • Time Complexity: O(V + E) where V is vertices and E is edges in the graph
  • Space Complexity: O(V) for the queue and visited set in the worst case
  • Common Applications:
    • Finding shortest path in unweighted graphs
    • Level-order tree traversal
    • Social network connectivity analysis
    • Puzzle solving and minimum moves problems

Problem Statement

Given a graph with nodes and edges, BFS starts from a chosen node and plunges through all neighbors level by level. Use the visualizer to run BFS step-by-step, observing how the queue drives the traversal and how the visited order expands outward from the start node.

queue_structure.txt

1// FIFO Queue used by BFS
2struct Queue {
3Node* front;
4Node* rear;
5bool[] visited;
6}
7
8// enqueue → rear, dequeue → front (first in first out)

bfs_anatomy.svg

A B C D Level 0 Level 1 Level 2

BFS on Tree — Example 1

tree.svg

Current
Visited
In Queue
Unvisited

Execution Mode

Queue

[ ]

Visited Order

[ ]
Ready to start

BFS on Graph — Example 2

graph.svg

Current
Visited
In Queue
Unvisited

Execution Info

Queue

[ ]

Visited Order

[ ]
Ready to start

Algorithm & Pseudocode

bfs_iterative.txt

1// BFS using explicit queue
2function bfs(graph, start):
3queue = [start]
4visited = set()
5result = []
6
7while queue is not empty:
8node = queue.dequeue()
9if node in visited: continue
10visited.add(node)
11result.append(node)
12for neighbor in graph[node]:
13if neighbor not in visited:
14queue.enqueue(neighbor)
15return result

bfs_explanation.txt

1// Key differences from DFS:
2// - Uses FIFO queue instead of LIFO stack
3// - Explores level-by-level outward
4// - Cannot use pure recursion
5
6// BFS guarantees shortest path in
7// unweighted graphs because:
8// - All nodes at distance d are visited
9// - Before any nodes at distance d+1
10// - This level-order guarantee is key!

complexity.md

Aspect Complexity
TimeO(V + E)
Space (Queue)O(V) — queue stores frontier
Visited SetO(V) — prevents revisiting

Implementation

bfs.c

1#include <stdio.h>
2#include <string.h>
3#define MAX_NODES 100
4
5// ── BFS using Queue ──────────────────────
6void bfs(int adj[][MAX_NODES], int start, int n) {
7int queue[MAX_NODES], front=0, rear=0;
8int visited[MAX_NODES] = {0};
9queue[rear++] = start; // enqueue start
10visited[start] = 1;
11while (front < rear) {
12int v = queue[front++]; // dequeue
13printf("%d ", v);
14for (int i = 0; i < n; i++)
15if (adj[v][i] && !visited[i]) {
16 visited[i] = 1;
17 queue[rear++] = i; // enqueue
18}
19}
20}

bfs_main.c

1int main() {
2// Create adjacency matrix
3int adj[5][5] = {
4{ 0, 1, 1, 0, 0 },
5{ 1, 0, 0, 1, 1 },
6{ 1, 0, 0, 1, 0 },
7{ 0, 1, 1, 0, 0 },
8{ 0, 1, 0, 0, 0 }
9};
10printf("BFS: ");
11bfs(adj, 0, 5);
12printf("\n");
13return 0;
14}