BFS Program in C – Breadth First Search with Example

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.

1. Start at the source node. Mark it as visited and add it to the queue.
2. Dequeue the front node. For each of its unvisited neighbors, mark them visited and enqueue them.
3. 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

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

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

• C Program to Implement Depth First Search (DFS)
• C Program for Binary Search Tree Creation and Traversals
• C Program to Find Minimum Spanning Tree (Prim’s Algorithm)
• C Program for Simple Queue Operations

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.