Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

Basic Implementation

basic.c

#include <stdio.h>

#define V 7
#define MAX_DEG 4

int main(void) {
    int adj[V][MAX_DEG] = {
        {-1, -1, -1, -1},
        { 2,  3, -1, -1},
        { 1,  4, -1, -1},
        { 1,  4, -1, -1},
        { 2,  3,  5, -1},
        { 4,  6, -1, -1},
        { 5, -1, -1, -1},
    };
    int src = 1;
    int dst = 6;
    int dist[V];
    int parent[V];
    for (int i = 0; i < V; ++i) {
        dist[i] = -1;
        parent[i] = 0;
    }
    dist[src] = 0;
    int queue[16];
    int qhead = 0;
    int qtail = 0;
    queue[qtail++] = src;
    while (qhead < qtail) {
        int v = queue[qhead++];
        for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
            int nb = adj[v][k];
            if (dist[nb] == -1) {
                dist[nb] = dist[v] + 1;
                parent[nb] = v;
                queue[qtail++] = nb;
            }
        }
    }
    int path[V];
    int path_n = 0;
    int node = dst;
    while (node != 0) {
        path[path_n++] = node;
        node = parent[node];
    }
    printf("[");
    for (int i = path_n - 1; i >= 0; --i) {
        if (i < path_n - 1) printf(", ");
        printf("%d", path[i]);
    }
    printf("]\n");
    printf("%d\n", dist[dst]);
    return 0;
}

Complexity

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

Implementation notes

C: dist[] initialised to -1 doubles as the visited check, parent[] records the predecessor (0 marks the source), and a ring of indices over a fixed queue[] array gives FIFO order.
The replay shows dist, parent, and the queue filling in, then the reconstructed path, matching the lesson spec.

layers equal distance BFS order equals distance in an unweighted graph.