BFS Algorithm in C – Adjacency Matrix and List with Example

Breadth First Search (BFS) is a graph traversal algorithm that explores nodes level by level — starting from a source, it visits all immediate neighbors first, then their neighbors, and so on. Because of this level-by-level behavior, BFS always finds the shortest path in an unweighted graph. It is used in GPS navigation, social network analysis (degrees of connection), web crawlers, and network broadcasting.

This page covers BFS in C with two complete programs: one using an adjacency matrix (simple, O(V²)) and one using an adjacency list (efficient, O(V+E)), plus a step-by-step trace, complexity analysis, and comparison with DFS.

How BFS Works

BFS uses a queue (FIFO) to decide which node to visit next.

1. Mark the start node visited and enqueue it.
2. Dequeue the front node. Visit each unvisited neighbor: mark it visited and enqueue it.
3. Repeat until the queue is empty.

Step-by-step trace

Graph: 4 nodes. Edges: 1–2, 1–3, 2–4. Start at node 1.

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 ]

Step 1: Visit 1, enqueue neighbors → queue: [2, 3]
Step 2: Dequeue 2, visit neighbors → queue: [3, 4]
Step 3: Dequeue 3, no new neighbors → queue: [4]
Step 4: Dequeue 4, no new neighbors → queue: []

Traversal order: 1 → 2 → 3 → 4

Program 1 – BFS Using Adjacency Matrix

The matrix stores a 1 at [i][j] if an edge exists between node i and node j. Time complexity: O(V²) because checking neighbors requires scanning a full row.

/* BFS using adjacency matrix — iterative, O(V²) */
#include <stdio.h>

#define MAX 20

int adj[MAX][MAX];
int visited[MAX];
int queue[MAX];
int front, rear;

void enqueue(int v) { queue[++rear] = v; }
int  dequeue(void)  { return queue[front++]; }
int  is_empty(void) { return front > rear; }

void bfs(int start, int n)
{
    int v, i;

    enqueue(start);
    visited[start] = 1;

    while (!is_empty()) {
        v = dequeue();
        printf("%d ", v);
        for (i = 1; i <= n; i++) {
            if (adj[v][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(i);
            }
        }
    }
    printf("\n");
}

int main(void)
{
    int n, i, j, start;

    printf("Enter number of vertices: ");
    scanf("%d", &n);

    printf("Enter adjacency matrix (%d x %d):\n", n, n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &adj[i][j]);

    printf("Enter starting vertex: ");
    scanf("%d", &start);

    front = 0;
    rear  = -1;

    printf("BFS traversal: ");
    bfs(start, n);

    return 0;
}

Sample Input and Output

Enter number of vertices: 4
Enter adjacency matrix (4 x 4):
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Enter starting vertex: 1
BFS traversal: 1 2 3 4

Program 2 – BFS Using Adjacency List

The adjacency list only stores actual edges — better for sparse graphs where V is large but edges are few. Time complexity: O(V+E).

Implementation: adj[v][0] stores the neighbor count for node v; adj[v][1..k] stores the neighbor IDs.

/* BFS using adjacency list — O(V + E) */
#include <stdio.h>

#define MAX     10
#define MAXEDGE 20

/* adj[v][0] = neighbor count, adj[v][1..k] = neighbor node IDs */
int adj[MAX + 1][MAX + 1];
int visited[MAX + 1];
int queue[MAXEDGE];

void add_edge(int u, int v)
{
    adj[u][++adj[u][0]] = v;
    adj[v][++adj[v][0]] = u;   /* undirected graph */
}

void bfs(int start)
{
    int front = 0, rear = -1;
    int v, i, nb;

    visited[start] = 1;
    queue[++rear] = start;

    printf("BFS from vertex %d: ", start);

    while (front <= rear) {
        v = queue[front++];
        printf("%d ", v);

        for (i = 1; i <= adj[v][0]; i++) {
            nb = adj[v][i];
            if (!visited[nb]) {
                visited[nb] = 1;
                queue[++rear] = nb;
            }
        }
    }
    printf("\n");
}

int main(void)
{
    int n, e, i, u, v, start;

    printf("Enter vertices and edges: ");
    scanf("%d %d", &n, &e);

    printf("Enter %d edges (u v):\n", e);
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        add_edge(u, v);
    }

    printf("Enter starting vertex: ");
    scanf("%d", &start);

    bfs(start);
    return 0;
}

Sample Input and Output

Enter vertices and edges: 6 7
Enter 7 edges (u v):
1 2
1 3
2 4
2 5
3 5
4 6
5 6
Enter starting vertex: 1
BFS from vertex 1: 1 2 3 4 5 6

How to Compile and Run

gcc -ansi -Wall -Wextra bfs_matrix.c -o bfs_matrix
./bfs_matrix

Time and Space Complexity

V = vertices, E = edges. For a dense graph where E ≈ V², both give similar performance. For a sparse graph (e.g., a road network where each city connects to 4–5 others), the list is dramatically faster.

BFS vs DFS — Key Differences

Applications of BFS

• Shortest path — GPS routing on unweighted road networks
• Social networks — finding people within N degrees of connection
• 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

Related Programs

• Depth First Search (DFS) in C
• Minimum Spanning Tree – Prim’s Algorithm in C
• Binary Search in C
• Stack Operations in C
• Recursion in C – Complete Guide

Recommended Books

• The C Programming Language – Kernighan & Ritchie (India) | Amazon.com
• C Programming: A Modern Approach – K.N. King (India) | Amazon.com

Practice graph algorithms with the C Programming Quiz App — 500+ MCQs covering BFS, DFS, sorting, pointers, and more.
Download on Google Play →