BFS Breadth First Search on Graph in DSA C

Mental Model

BFS explores all neighbors of a node before moving to the next level of nodes. It spreads out evenly like ripples in water.

Analogy: Imagine dropping a stone in a pond. The ripples spread out evenly in circles, visiting all points at the same distance before moving further.

Graph:
  1
 / \
2   3
|    \
4     5

Queue: []
Visited: {}

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-4, 3-5; start BFS from node 1

Goal: Visit all nodes in order of their distance from node 1

Step 1: Start BFS at node 1, enqueue it, mark visited

Queue: [1]
Visited: {1}

Why: We begin from the start node to explore its neighbors

Step 2: Dequeue node 1, enqueue neighbors 2 and 3, mark visited

Queue: [2, 3]
Visited: {1, 2, 3}

Why: Visit all neighbors of node 1 before moving deeper

Step 3: Dequeue node 2, enqueue neighbor 4, mark visited

Queue: [3, 4]
Visited: {1, 2, 3, 4}

Why: Explore neighbors of node 2 next

Step 4: Dequeue node 3, enqueue neighbor 5, mark visited

Queue: [4, 5]
Visited: {1, 2, 3, 4, 5}

Why: Explore neighbors of node 3 next

Step 5: Dequeue node 4, no new neighbors to enqueue

Queue: [5]
Visited: {1, 2, 3, 4, 5}

Why: Node 4 has no unvisited neighbors

Step 6: Dequeue node 5, no new neighbors to enqueue

Queue: []
Visited: {1, 2, 3, 4, 5}

Why: Node 5 has no unvisited neighbors

Result:

Visited order: 1 -> 2 -> 3 -> 4 -> 5

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

// Graph represented as adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX_NODES];
int visited[MAX_NODES];

// Queue for BFS
typedef struct Queue {
    int items[MAX_NODES];
    int front;
    int rear;
} Queue;

void enqueue(Queue* q, int value) {
    q->items[++q->rear] = value; // add to rear
}

int dequeue(Queue* q) {
    return q->items[++q->front]; // remove from front
}

int isEmpty(Queue* q) {
    return q->front == q->rear;
}

Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;
}

void bfs(int start, int n) {
    Queue q;
    q.front = -1;
    q.rear = -1;

    visited[start] = 1; // mark start visited
    enqueue(&q, start); // enqueue start

    while (!isEmpty(&q)) {
        int current = dequeue(&q); // dequeue front
        printf("%d -> ", current); // print current node

        Node* temp = graph[current];
        while (temp) {
            if (!visited[temp->vertex]) {
                visited[temp->vertex] = 1; // mark visited
                enqueue(&q, temp->vertex); // enqueue neighbor
            }
            temp = temp->next; // move to next neighbor
        }
    }
    printf("null\n");
}

int main() {
    int n = 5; // number of nodes

    // Initialize graph
    for (int i = 0; i <= n; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }

    // Add edges
    addEdge(1, 3);
    addEdge(1, 2);
    addEdge(2, 4);
    addEdge(3, 5);

    // Run BFS from node 1
    bfs(1, n);

    return 0;
}

visited[start] = 1; // mark start visited enqueue(&q, start); // enqueue start

mark start node visited and add it to queue to begin BFS

while (!isEmpty(&q)) {

continue until all reachable nodes are visited

int current = dequeue(&q);

remove front node from queue to process it

printf("%d -> ", current);

print current node in BFS order

while (temp) { if (!visited[temp->vertex]) { visited[temp->vertex] = 1; enqueue(&q, temp->vertex); } temp = temp->next; }

visit all unvisited neighbors, mark visited, enqueue for later processing

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for the queue and visited array to track nodes

vs Alternative: Compared to DFS which uses a stack or recursion, BFS uses a queue and explores level by level, useful for shortest path in unweighted graphs

Edge Cases

Empty graph (no nodes)

BFS does nothing as there are no nodes to visit

DSA C

while (!isEmpty(&q)) {

Graph with isolated nodes

BFS visits only nodes reachable from start node, isolated nodes remain unvisited

DSA C

while (!isEmpty(&q)) {

Graph with cycles

Visited array prevents revisiting nodes, avoiding infinite loops

DSA C

if (!visited[temp->vertex]) {

When to Use This Pattern

When you need to explore nodes layer by layer or find shortest paths in unweighted graphs, BFS is the pattern to use because it visits neighbors first before going deeper.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing causes repeated visits and infinite loops
Fix: Mark nodes visited immediately when enqueueing to avoid duplicates

Mistake: Using stack instead of queue changes BFS to DFS behavior
Fix: Use a queue data structure to maintain correct BFS order

Summary

BFS visits all nodes in a graph level by level starting from a given node.

Use BFS when you want to explore nodes in order of their distance or find shortest paths in unweighted graphs.

The key insight is to use a queue to explore neighbors first before moving deeper.