Graphs

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.

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

Basic Implementation

basic.c
Replay: real traced execution (multi-file project)
#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;
}

  1. dist ← {1: 0}

    23}24dist[src] = 0;25int queue[16];
    values this step{1: 0}dist

  2. parent ← {1: null}

    21    dist[i] = -1;22    parent[i] = 0;23}
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    29while (qhead < qtail) {30    int v = queue[qhead++];31    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    29while (qhead < qtail) {30    int v = queue[qhead++];31    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    29while (qhead < qtail) {30    int v = queue[qhead++];31    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    29while (qhead < qtail) {30    int v = queue[qhead++];31    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    29while (qhead < qtail) {30    int v = queue[qhead++];31    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    29while (qhead < qtail) {30    int v = queue[qhead++];31    for (int k = 0; k < MAX_DEG && adj[v][k] != -1; ++k) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    47printf("[");48for (int i = path_n - 1; i >= 0; --i) {49    if (i < path_n - 1) printf(", ");
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← [1, 2, 4, 5, 6]

    51}52printf("]\n");53printf("%d\n", dist[dst]);
    values this step[1, 2, 4, 5, 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    52printf("]\n");53printf("%d\n", dist[dst]);54return 0;
    values this step4stdout4dist[6]

  12. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    52printf("]\n");53printf("%d\n", dist[dst]);54return 0;
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

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. It also contrasts that unweighted result with a weighted graph where Dijkstra with a priority queue is required.