Breadth-First Search

Graphs O(V + E) O(V)

Explores a graph level by level using a queue — the backbone of shortest paths in unweighted graphs.

Start node

1/47

Mark source 0 as visited.

InvariantThe queue holds nodes of at most two adjacent layers, so nodes come out in non-decreasing distance from the source.

currentfrontiervisitedtree edge

bfs.c

#define V 6
 
void bfs(int graph[V][V], int start) {
    int visited[V] = {0};
    int queue[V], front = 0, rear = 0;
 
    visited[start] = 1;
    queue[rear++] = start;
 
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
        }
    }
}

How Breadth-First Search works

Explore outward in rings: visit all nodes at distance 1, then 2, and so on, using a FIFO queue. The first time you reach a node is via a shortest edge-count path.

When to use it

Shortest paths in unweighted graphs, level-order processing, connectivity checks.