Breadth-first search (BFS) using a queue

BFS explores a graph level by level: visit the start vertex, then all neighbors, then their unvisited neighbors, and so on. A queue (FIFO) holds the frontier of vertices waiting to be processed. A visited array prevents re-enqueueing.

1) Why a queue?

Vertices discovered earlier must be processed before those discovered later. That is exactly FIFO behavior. DFS uses a stack (or recursion) instead.

2) BFS outline

3) Example in C

Undirected graph with 5 vertices (0–4). Edges: 0–1, 0–2, 1–3, 2–4 (adjacency lists below).

#include <stdio.h>
#include <string.h>

#define V 5
#define MAXE 16

static int adj[V][MAXE];
static int deg[V];

static void add_edge(int a, int b) {
    adj[a][deg[a]++] = b;
    adj[b][deg[b]++] = a;
}

int main(void) {
    int q[V * V], front = 0, rear = 0;
    int vis[V];
    memset(vis, 0, sizeof vis);

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
    add_edge(2, 4);

    int start = 0;
    vis[start] = 1;
    q[rear++] = start;

    printf("BFS order: ");
    while (front < rear) {
        int u = q[front++];
        printf("%d ", u);
        for (int i = 0; i < deg[u]; i++) {
            int v = adj[u][i];
            if (!vis[v]) {
                vis[v] = 1;
                q[rear++] = v;
            }
        }
    }
    printf("\n");
    return 0;
}

Graph structure

Visual graph

        3
        |
        1
        |
    0 --- 2 --- 4

BFS traversal step-by-step

BFS order output

Final output

BFS order: 0 1 2 3 4

Key observations

Important note: The graph is not disconnected; all vertices are reachable from start vertex 0 via paths through 1 and 2.

Execution summary

Printed line: BFS order: 0 1 2 3 4 (neighbor order follows how edges were stored in each adjacency list).

4) Complexity

• Time: each vertex dequeued once, each edge examined twice in undirected graph → O(V + E).
• Space: visited O(V), queue O(V) in worst case — see space complexity.