Graphs

Build a Graph as an Adjacency List

Represent an undirected graph as a per-vertex list of neighbours. For every edge (u, v), append v to adj[u] and u to adj[v]. Neighbour lists keep insertion order so the graph is a stable, deterministic fixture for the search lessons.

Algorithm

Basic Implementation

basic.c 
#include <stdio.h>

#define V 7
#define MAX_DEG 4

int main(void) {
    int edges[6][2] = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}};
    int adj[V][MAX_DEG];
    int deg[V] = {0};
    for (int e = 0; e < 6; ++e) {
        int u = edges[e][0];
        int w = edges[e][1];
        adj[u][deg[u]++] = w;
        adj[w][deg[w]++] = u;
    }
    printf("{");
    for (int v = 1; v < V; ++v) {
        if (v > 1) printf(", ");
        printf("%d: [", v);
        for (int k = 0; k < deg[v]; ++k) {
            if (k > 0) printf(", ");
            printf("%d", adj[v][k]);
        }
        printf("]");
    }
    printf("}\n");
    return 0;
}

The graph fixture is pinned once, then the adjacency list writes each undirected edge in both directions.

Step 1 - Pinned graph fixture

The six vertices and six undirected edges are the shared fixture for BFS and DFS.

Graph with edges (1,2), (1,3), (2,4), (3,4), (4,5), (5,6).123456

Step 2 - Final adjacency list

Each row lists neighbours in the same insertion order used by the lesson.

Adjacency list after all six undirected edges are inserted.vertexneighbours1[2, 3]2[1, 4]3[1, 4]4[2, 3, 5]5[4, 6]6[5]

Complexity

  • Build: O(V + E)
  • Space: O(V + E)

Implementation notes

  • C: a fixed adj[V][MAX_DEG] array with a per-vertex deg[] count stores neighbours in edge order; vertices are indexed 1..6 (index 0 unused).
  • The replay shows the adjacency list after each edge is added, matching the lesson spec.
adjacency list Each edge adds two directed entries, one in each direction.