C Program for BFS (Breadth First Search) with Example

A C program for BFS uses a queue to explore nodes level by level; the code initializes a queue, marks the start node visited, then repeatedly dequeues a node, prints it, and enqueues its unvisited neighbors using enqueue and dequeue functions.

Examples

InputGraph edges: 0-1, 0-2, 1-2, 2-0, 2-3, 3-3; Start node: 2

Output2 0 3 1

InputGraph edges: 0-1, 1-2, 2-3; Start node: 0

Output0 1 2 3

InputGraph edges: 0-1; Start node: 1

Output1

How to Think About It

To perform BFS, think of visiting nodes in layers starting from a chosen node. Use a queue to keep track of nodes to visit next. Mark nodes as visited when you add them to the queue to avoid repeats. Then, take nodes from the queue one by one, visit their neighbors, and add unvisited neighbors to the queue until all reachable nodes are visited.

Algorithm

1

Initialize a queue and a visited array to false for all nodes.

2

Mark the start node as visited and enqueue it.

3

While the queue is not empty, do:

4

Dequeue a node and print it.

5

For each neighbor of this node, if not visited, mark visited and enqueue it.

Code

c

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;
bool visited[MAX] = {false};
int graph[MAX][MAX] = {
    {0,1,1,0,0},
    {1,0,1,1,0},
    {1,1,0,1,0},
    {0,1,1,0,1},
    {0,0,0,1,0}
};

void enqueue(int val) {
    if (rear == MAX - 1) return;
    if (front == -1) front = 0;
    queue[++rear] = val;
}

int dequeue() {
    if (front == -1 || front > rear) return -1;
    return queue[front++];
}

void bfs(int start) {
    enqueue(start);
    visited[start] = true;
    while (front <= rear) {
        int current = dequeue();
        if (current == -1) break;
        printf("%d ", current);
        for (int i = 0; i < MAX; i++) {
            if (graph[current][i] && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
}

int main() {
    bfs(0);
    return 0;
}

Output

0 1 2 3 4 

Dry Run

Let's trace BFS starting from node 0 on the given graph.

1

Initialize

Queue: empty, visited: all false

2

Start BFS

Enqueue 0, visited[0] = true; Queue: [0]

3

Dequeue 0

Print 0; Check neighbors 1 and 2; enqueue 1 and 2; visited[1]=true, visited[2]=true; Queue: [1,2]

4

Dequeue 1

Print 1; Check neighbors 0,2,3; 0 and 2 visited; enqueue 3; visited[3]=true; Queue: [2,3]

5

Dequeue 2

Print 2; Check neighbors 0,1,3; all visited; Queue: [3]

6

Dequeue 3

Print 3; Check neighbors 1,2,4; 1 and 2 visited; enqueue 4; visited[4]=true; Queue: [4]

7

Dequeue 4

Print 4; Check neighbor 3 visited; Queue empty; End

Queue	Visited nodes	Printed nodes
[0]	[0]
[1,2]	[0,1,2]	0
[2,3]	[0,1,2,3]	0 1
[3]	[0,1,2,3]	0 1 2
[4]	[0,1,2,3,4]	0 1 2 3
[]	[0,1,2,3,4]	0 1 2 3 4

Why This Works

Step 1: Use a queue to track nodes

BFS uses a queue to explore nodes in the order they are discovered, ensuring nodes closer to the start are visited first.

Step 2: Mark nodes visited when enqueued

Marking nodes as visited when adding to the queue prevents revisiting and infinite loops.

Step 3: Process nodes until queue empty

Dequeue nodes one by one, print them, and enqueue their unvisited neighbors to cover the graph layer by layer.

Alternative Approaches

Recursive BFS using a queue

c

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

int graph[MAX][MAX] = {
    {0,1,1,0,0},
    {1,0,1,1,0},
    {1,1,0,1,0},
    {0,1,1,0,1},
    {0,0,0,1,0}
};
bool visited[MAX] = {false};

void bfs_recursive(int queue[], int front, int rear) {
    if (front > rear) return;
    int current = queue[front];
    printf("%d ", current);
    for (int i = 0; i < MAX; i++) {
        if (graph[current][i] && !visited[i]) {
            visited[i] = true;
            queue[++rear] = i;
        }
    }
    bfs_recursive(queue, front + 1, rear);
}

int main() {
    int queue[MAX];
    int front = 0, rear = 0;
    queue[rear] = 0;
    visited[0] = true;
    bfs_recursive(queue, front, rear);
    return 0;
}

Uses recursion to process the queue instead of a loop; may be less intuitive and risks stack overflow on large graphs.

BFS using adjacency list

c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjacencyList[MAX];
bool visited[MAX] = {false};

typedef struct Queue {
    int items[MAX];
    int front, rear;
} Queue;

void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1) return;
    if (q->front == -1) q->front = 0;
    q->items[++q->rear] = value;
}

int dequeue(Queue* q) {
    if (q->front == -1 || q->front > q->rear) return -1;
    return q->items[q->front++];
}

void addEdge(int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;
}

void bfs(int start) {
    Queue q = {.front = -1, .rear = -1};
    enqueue(&q, start);
    visited[start] = true;
    while (q.front <= q.rear) {
        int current = dequeue(&q);
        if (current == -1) break;
        printf("%d ", current);
        Node* temp = adjacencyList[current];
        while (temp) {
            if (!visited[temp->vertex]) {
                enqueue(&q, temp->vertex);
                visited[temp->vertex] = true;
            }
            temp = temp->next;
        }
    }
}

int main() {
    for (int i = 0; i < MAX; i++) adjacencyList[i] = NULL;
    addEdge(0,1); addEdge(0,2);
    addEdge(1,0); addEdge(1,2); addEdge(1,3);
    addEdge(2,0); addEdge(2,1); addEdge(2,3);
    addEdge(3,1); addEdge(3,2); addEdge(3,4);
    addEdge(4,3);
    bfs(0);
    return 0;
}

Uses adjacency list for memory efficiency on sparse graphs; more complex setup but better for large graphs.

Complexity: O(V + E) time, O(V) space

Time Complexity

BFS visits each vertex once and checks all edges once, so the time is proportional to vertices plus edges, O(V + E).

Space Complexity

The queue and visited array use space proportional to the number of vertices, O(V).

Which Approach is Fastest?

Using adjacency lists is generally faster and more memory efficient for sparse graphs compared to adjacency matrices.

Approach	Time	Space	Best For
Adjacency Matrix BFS	O(V^2)	O(V^2)	Dense graphs or small graphs
Adjacency List BFS	O(V + E)	O(V + E)	Sparse graphs and large graphs
Recursive BFS	O(V + E)	O(V) + call stack	Small graphs; less common