Graph Traversal Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph level by level. It starts from a source vertex, visits all its immediate neighbors (distance 1), then visits the neighbors of those neighbors (distance 2), and so on.

Imagine dropping a pebble into a still pond. The ripples spread outwards in concentric circles, layer by layer. That is exactly how BFS works – it expands outward from the starting point, layer by layer.

BFS uses a queue data structure to keep track of which vertices to visit next. This FIFO (First-In-First-Out) property ensures that vertices are explored in the order they are discovered.

How BFS Works?

1. Start by choosing a source vertex and marking it as visited.
2. Enqueue the source vertex into a queue.
3. While the queue is not empty:
   • Dequeue a vertex from the front of the queue – this is the current vertex.
   • Explore all its unvisited neighbors:
     • Mark them as visited.
     • Enqueue them into the queue.
4. Repeat step 3 until the queue is empty.

Detailed Example: BFS Step-by-Step

Consider the following undirected graph:

        0
       / \
      1   2
     / \   \
    3   4   5

We want to perform BFS starting from vertex 0.

Initial State

• Queue: [] (empty)
• Visited: {} (empty set)
• Result (order of traversal): []

Step-by-Step Execution

Final BFS Traversal Order: 0 → 1 → 2 → 3 → 4 → 5

Visualizing the Levels

• Level 0 (Distance 0): {0}
• Level 1 (Distance 1): {1, 2}
• Level 2 (Distance 2): {3, 4, 5}

BFS finds the shortest path in terms of the number of edges from the source to any vertex.

Algorithm for BFS

Pseudocode

Algorithm: BFS(G, source)
Input:  G - Graph
        source - Starting vertex
Output: BFS traversal order

Step 1: START
Step 2: Create a queue Q
Step 3: Mark source as visited
Step 4: Enqueue source into Q
Step 5: WHILE Q is not empty DO
Step 6:     current = Dequeue from Q
Step 7:     Process current (print or store)
Step 8:     FOR each neighbor v of current DO
Step 9:         IF v is not visited THEN
Step 10:            Mark v as visited
Step 11:            Enqueue v into Q
Step 12:        END IF
Step 13:    END FOR
Step 14: END WHILE
Step 15: END

Implementation in C Programming

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

// Graph structure using Adjacency List (for efficiency)
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int vertices;
    Node** adjLists;
} Graph;

// Queue structure for BFS
typedef struct Queue {
    int items[MAX];
    int front, rear;
} Queue;

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

// Create a graph
Graph* createGraph(int v) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = v;
    graph->adjLists = (Node**)malloc(v * sizeof(Node*));
    for (int i = 0; i < v; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// Add edge (undirected)
void addEdge(Graph* graph, int u, int v) {
    // Add v to u's list
    Node* newNode = createNode(v);
    newNode->next = graph->adjLists[u];
    graph->adjLists[u] = newNode;
    // Add u to v's list (for undirected)
    newNode = createNode(u);
    newNode->next = graph->adjLists[v];
    graph->adjLists[v] = newNode;
}

// Queue functions
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

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

void enqueue(Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        // Last element in queue
        q->front = -1;
        q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

// BFS function
void BFS(Graph* graph, int start) {
    // Create visited array
    int* visited = (int*)calloc(graph->vertices, sizeof(int));
    Queue q;
    initQueue(&q);
    
    // Mark start as visited and enqueue it
    visited[start] = 1;
    enqueue(&q, start);
    
    printf("BFS Traversal: ");
    
    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        printf("%d ", current);
        
        // Explore all neighbors of current
        Node* temp = graph->adjLists[current];
        while (temp != NULL) {
            int neighbor = temp->vertex;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                enqueue(&q, neighbor);
            }
            temp = temp->next;
        }
    }
    printf("\n");
    free(visited);
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 5);
    
    BFS(graph, 0);
    
    return 0;
}

Output:

BFS Traversal: 0 1 2 3 4 5

Complexity Analysis

Time Complexity

• O(V + E) – where V is the number of vertices and E is the number of edges.
• Each vertex is enqueued and dequeued exactly once (O(V)).
• Each edge is examined twice (in an undirected graph) or once (in a directed graph) (O(E)).

Space Complexity

• O(V) – for the visited array, the queue, and the adjacency list storage (excluding the graph itself).
• The queue can, in the worst case, hold all vertices (e.g., a star graph where the center is the source).

Advantages of BFS

1. Guaranteed Shortest Path: In unweighted graphs, BFS finds the shortest path (minimum number of edges) from the source to every other vertex.
2. Complete: If a path exists, BFS will find it (it explores all possibilities).
3. Level-Order Traversal: Useful for problems like finding the minimum depth of a tree or social network hop distance.

Disadvantages of BFS

1. Memory Intensive: Requires storing all vertices at the current level in the queue, which can be large for wide graphs.
2. Not Suitable for Weighted Graphs: BFS does not account for edge weights; it only minimizes the number of edges.
3. Slower for Deep Graphs: If the target is very deep (far from the source), BFS may explore many shallow vertices before reaching it, which can be wasteful compared to DFS.

Real-World Applications of BFS