Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.c

#include <stdio.h>
#include <stdbool.h>

#define V 7
#define MAX_DEG 4

int main(void) {
    int adj[V][MAX_DEG] = {
        {-1, -1, -1, -1},   // index 0 unused
        { 2,  3, -1, -1},   // 1 -> [2, 3]
        { 1,  4, -1, -1},   // 2 -> [1, 4]
        { 1,  4, -1, -1},   // 3 -> [1, 4]
        { 2,  3,  5, -1},   // 4 -> [2, 3, 5]
        { 4,  6, -1, -1},   // 5 -> [4, 6]
        { 5, -1, -1, -1},   // 6 -> [5]
    };
    int start = 1;
    bool visited[V] = {false};
    visited[start] = true;
    int queue[16];
    int qhead = 0;
    int qtail = 0;
    queue[qtail++] = start;
    int order[V];
    int order_n = 0;
    while (qhead < qtail) {
        int v = queue[qhead++];
        order[order_n++] = v;
        for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
            int nb = adj[v][k];
            if (!visited[nb]) {
                visited[nb] = true;
                queue[qtail++] = nb;
            }
        }
    }
    printf("[");
    for (int i = 0; i < order_n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", order[i]);
    }
    printf("]\n");
    return 0;
}

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

C: a fixed-size int adj[V][MAX_DEG] array with -1 sentinels documents the adjacency list deterministically; vertex iteration walks the row in declared order. C has no built-in map, queue, or set, so flat arrays are the smallest honest containers for the lesson.
A bool visited[V] array is the explicit "visited" set, indexed by vertex id; the queue is a plain int queue[16] with qhead / qtail indices.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain `int queue[16]` array with `qhead` / `qtail` indices implements FIFO enqueue/dequeue without hiding the iteration shape.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.