Graphs

Introduction

A graph is a set of vertices (nodes) joined by edges. Roads between cities, friendships, links between web pages and the wires of a network are all graphs. Trees and linked lists are special kinds of graph.

• In an undirected graph an edge goes both ways (a friendship). In a directed graph it has a direction (following someone).
• A weighted graph gives each edge a number: a distance, a cost, a time.
• The degree of a vertex is the number of edges that touch it.

We number the vertices 0 to n-1. There are two standard ways to store the edges.

Lists and trees have strict shapes, but connections in the real world do not. Roads form loops, and friendships go in every direction. A graph puts no limit on what connects to what, so it can model nearly anything.

How it works

Adjacency matrix

#include <stdio.h>
#define N 4

int main(void) {
    int adj[N][N] = {0};
    int edges[4][2] = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
    for (int e = 0; e < 4; e++) {
        int u = edges[e][0], v = edges[e][1];
        adj[u][v] = 1;
        adj[v][u] = 1;   // undirected: both directions
    }
    for (int u = 0; u < N; u++) {
        printf("%d:", u);
        for (int v = 0; v < N; v++)
            if (adj[u][v]) printf(" %d", v);
        printf("\n");
    }
    return 0;
}

adj[u][v] is 1 when there is an edge from u to v. For an undirected graph, set both adj[u][v] and adj[v][u], so the matrix is symmetric. Checking one edge is O(1), but the matrix always takes n² cells, even when there are few edges, and listing a vertex's neighbours means scanning a whole row.

Syntax

typedef struct edge {
    int to;
    struct edge *next;
} Edge;

Edge *adj[N];   // adj[u] is the list of u's neighbours

Example

#include <stdio.h>
#include <stdlib.h>
#define N 4

typedef struct edge {
    int to;
    struct edge *next;
} Edge;

Edge *adj[N];   // adj[u] is the list of u's neighbours

void add_edge(int u, int v) {
    Edge *e = malloc(sizeof(Edge));
    e->to = v;
    e->next = adj[u];
    adj[u] = e;
}

void connect(int u, int v) {   // undirected: an edge each way
    add_edge(u, v);
    add_edge(v, u);
}

int main(void) {
    connect(0, 1);
    connect(0, 2);
    connect(2, 3);
    for (int u = 0; u < N; u++) {
        int degree = 0;
        printf("%d:", u);
        for (Edge *e = adj[u]; e != NULL; e = e->next) {
            printf(" %d", e->to);
            degree++;
        }
        printf("  (degree %d)\n", degree);
    }
    return 0;
}

adj[u] is a linked list of u's neighbours. It takes memory only for the edges that exist: O(n + m) for n vertices and m edges. Listing neighbours is fast; checking one edge means walking a list.

Line by line

1. Edge is one entry in a neighbour list: the vertex it goes to, and the next entry.
2. adj holds one list head per vertex, and every list starts as NULL.
3. add_edge puts a new entry at the front of u's list.
4. connect adds the edge in both directions, because the graph is undirected.
5. main makes three connections, then loops over the vertices.
6. For each vertex it walks the list, prints each neighbour and counts them. Newer edges come first, so neighbours are not in sorted order.

Expected result

0: 2 1  (degree 2)
1: 0  (degree 1)
2: 3 0  (degree 2)
3: 2  (degree 1)

In the real world

Maps, social networks and the web itself are huge graphs, so their software depends on storing edges compactly. Most of these graphs are sparse: a person knows only a tiny fraction of all people, which is why adjacency lists are the usual choice.

Common mistakes

• For an undirected graph, adding the edge in only one direction.
• Numbering vertices from 1 but making the array size n, so vertex n is out of bounds.
• Using a matrix for a huge sparse graph: 100,000 vertices need 10 billion cells.

Best practices

• Number vertices from 0, or make the arrays one larger.
• Add undirected edges in both directions from one helper function.
• Think about the number of edges before reaching for a matrix.

Summary

A graph is a set of vertices joined by edges. An adjacency matrix answers "is there an edge?" in O(1) using n² cells, and adjacency lists use O(n + m) memory and visit a vertex's neighbours quickly.

Mark lesson complete