Breadth first traversal in graph

Breadth first traversal (BFS) visits a graph level by level. Starting from a source vertex, it visits the source, then all vertices at distance 1, then distance 2, and so on. A queue (FIFO) holds the vertices waiting to be explored, and a visited array prevents revisiting.

Algorithm

BFS(G, s)
1. mark s visited; enqueue s
2. while queue not empty
3.     v = dequeue(); print v
4.     for each neighbour w of v
5.         if w not visited: mark w visited; enqueue w

Implementation

Keep three structures: an adjacency matrix or lists for the graph, a visited[] array, and a circular or linear queue.

int adj[N][N], visited[N], n;
void bfs(int s) {
    int queue[N], front = 0, rear = 0;
    visited[s] = 1; queue[rear++] = s;
    while (front < rear) {
        int v = queue[front++];            /* dequeue */
        printf("%d ", v);
        for (int w = 0; w < n; w++)
            if (adj[v][w] && !visited[w]) {
                visited[w] = 1;
                queue[rear++] = w;         /* enqueue */
            }
    }
}

Example

        A
       / \
      B   C
     / \   \
    D   E---F

Edges: A-B, A-C, B-D, B-E, C-F, E-F. Adjacency lists (alphabetical): A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E.

Start from A:

BFS order: A B C D E F

Complexity: O(V + E) with adjacency lists, O(V²) with an adjacency matrix. BFS finds shortest paths (fewest edges) in an unweighted graph and is used for connected components and level-order search.