Breadth First Search (BFS) is a graph traversal algorithm that visits every node in a graph level by level — starting from a source node, it explores all immediate neighbors first, then their neighbors, and so on. Because of this level-by-level behavior, BFS always finds the shortest path between two nodes in an unweighted graph.
BFS is used in real-world applications like social network friend suggestions (finding people within N degrees of connection), GPS navigation (shortest route), and network broadcasting.
How BFS Works — Step by Step
BFS uses a queue (First In, First Out) to track which node to visit next.
- Start at the source node. Mark it as visited and add it to the queue.
- Dequeue the front node. For each of its unvisited neighbors, mark them visited and enqueue them.
- Repeat step 2 until the queue is empty.
Example: Consider a graph with 4 nodes where node 1 connects to 2 and 3, and node 2 connects to 4.
Adjacency Matrix:
1 2 3 4
1 [ 0 1 1 0 ]
2 [ 1 0 0 1 ]
3 [ 1 0 0 0 ]
4 [ 0 1 0 0 ]
BFS from node 1:
Step 1: Visit 1, queue = [2, 3]
Step 2: Visit 2, queue = [3, 4]
Step 3: Visit 3, queue = [4]
Step 4: Visit 4, queue = []
Traversal order: 1 → 2 → 3 → 4
C Program for BFS (Breadth First Search)
The program below uses an adjacency matrix to represent the graph. A value of 1 at position [i][j] means there is an edge from node i to node j.
#include <stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;
void bfs(int v) {
for (i = 1; i <= n; i++)
if (a[v][i] && !visited[i]) {
q[++r] = i;
visited[i] = 1;
}
if (f <= r)
bfs(q[f++]);
}
int main() {
int v;
printf("Enter the number of vertices: ");
scanf("%d", &n);
for (i = 1; i <= n; i++) {
q[i] = 0;
visited[i] = 0;
}
printf("Enter the adjacency matrix (%d x %d):\n", n, n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &v);
visited[v] = 1;
bfs(v);
printf("Visited nodes: ");
for (i = 1; i <= n; i++)
if (visited[i])
printf("%d ", i);
printf("\n");
return 0;
}
Code Explanation
- Adjacency matrix
a[20][20]: Stores the graph. a[i][j] = 1 means an edge exists between node i and node j.
- Queue
q[] with front f and rear r: Nodes waiting to be processed. f points to the front (next to dequeue), r to the rear (last enqueued).
visited[] array: Prevents revisiting nodes. A node is marked visited when enqueued, not when processed — this avoids adding duplicates to the queue.- Recursive
bfs(v): Enqueues all unvisited neighbors of v, then recurses on the next node in the queue. This mimics the iterative dequeue-process loop.
Sample Input and Output
Enter the number of vertices: 4
Enter the adjacency matrix (4 x 4):
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Enter the starting vertex: 1
Visited nodes: 1 2 3 4
All 4 nodes are reachable from vertex 1, so BFS visits all of them in level order.
Time and Space Complexity
| Case |
Time Complexity |
Space Complexity |
| Adjacency Matrix |
O(V²) |
O(V) |
| Adjacency List |
O(V + E) |
O(V) |
Where V = number of vertices and E = number of edges. This program uses an adjacency matrix, so the time complexity is O(V²). For sparse graphs (few edges), an adjacency list implementation gives better performance at O(V + E).
Space complexity is O(V) for the queue and visited array.
BFS vs DFS — Key Differences
| Property |
BFS |
DFS |
| Data structure |
Queue (FIFO) |
Stack (LIFO) or recursion |
| Traversal order |
Level by level |
As deep as possible first |
| Shortest path |
Yes (unweighted graphs) |
No |
| Memory usage |
Higher (stores all neighbors) |
Lower (stores one path) |
| Best for |
Shortest path, peer networks |
Topological sort, cycle detection |
Applications of BFS
- Shortest path in unweighted graphs — GPS routing on maps with equal-cost roads
- Social networks — finding people within N degrees of connection (LinkedIn, Facebook)
- Web crawlers — crawling links level by level from a seed URL
- Network broadcasting — sending packets to all nodes in a network
- Puzzle solving — finding minimum moves in sliding puzzles, Rubik’s cube
Related Programs
As an Amazon Associate we earn from qualifying purchases.
Further Reading
The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.
