Graph representations: adjacency matrix, adjacency list, incidence matrix

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What is Σ deg(v) in an undirected graph with e edges? from Lesson 6.1
• What does bottom-up build-heap cost? from Lesson 5.3
• How do you insert a node at the head of a singly linked list? from Lesson 3.4.1

1 · The Hook

🎣

A city keeps its road network in two ways: a big grid with a tick wherever two junctions are directly connected (easy to check one pair, wasteful when roads are few), and a notebook with one page per junction listing its neighbours (compact, but checking one pair means reading a page).

2 · Predict First

🤔

In an adjacency matrix of a simple undirected graph with e edges, how many entries are 1? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

2e: each edge {u, v} sets both g[u][v] and g[v][u]. The matrix is symmetric with zeros on the diagonal.

Adjacency matrix

An n × n array: g[u][v] = 1 if there is an edge u–v (or the weight, in a weighted graph), else 0. Undirected ⇒ symmetric. Row sum = degree (out-degree for directed); column sum = in-degree.

#define N 8
int g[N][N];                              /* adjacency matrix, all 0 at start */

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int m = 8, i, j, deg, sum = 0;
    for (i = 0; i < m; i++) {
        g[e[i][0]][e[i][1]] = 1;          /* undirected: set both entries */
        g[e[i][1]][e[i][0]] = 1;
    }
    for (i = 0; i < N; i++) {
        deg = 0;
        for (j = 0; j < N; j++) deg += g[i][j];   /* row sum = degree */
        printf("%d ", deg);
        sum += deg;
    }
    printf("| %d\n", sum / 2);
    return 0;
}

Output

2 3 2 2 3 2 1 1 | 8

Adjacency list

An array of n linked lists; list u holds the neighbours of u. Space Θ(n + e) (each undirected edge appears twice). If new neighbours are inserted at the head, each list ends up in reverse order of the edge input — this changes traversal orders (Lesson 6.3).

#define N 8
struct node {
    int v;
    struct node *next;
};
struct node *adj[N];                      /* adjacency lists, all NULL at start */

void addEdge(int a, int b)                /* insert b at the head of a's list */
{
    struct node *p = malloc(sizeof(struct node));
    p->v = b;
    p->next = adj[a];
    adj[a] = p;
}

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    struct node *p;
    for (i = 0; i < 8; i++) {
        addEdge(e[i][0], e[i][1]);
        addEdge(e[i][1], e[i][0]);
    }
    for (i = 0; i < 6; i++) {
        printf("%d:", i);
        for (p = adj[i]; p != NULL; p = p->next) printf(" %d", p->v);
        printf("\n");
    }
    return 0;
}

Output

0: 2 1
1: 4 3 0
2: 4 0
3: 5 1
4: 5 2 1
5: 4 3

Incidence matrix

An n × e array: entry [v][k] = 1 if vertex v is an end of edge k. Each column of an undirected incidence matrix has exactly two 1s; row sums are degrees. (Directed versions mark one end +1 and the other −1; the sign convention varies.)

Which one?

Matrix fact: in A², entry [i][j] counts the walks of length 2 from i to j (common neighbours when i ≠ j); the diagonal of A² holds the degrees. In the example, A²[1][2] = 2 (common neighbours 0 and 4), A²[1][1] = 3 = deg(1).

4 · Visual

Running example: 8 vertices, 8 edges, two connected components.

adjacency matrix (rows 0..7)          adjacency lists (head insertion)

     0 1 2 3 4 5 6 7
  0  0 1 1 0 0 0 0 0                   0 -> 2 -> 1
  1  1 0 0 1 1 0 0 0                   1 -> 4 -> 3 -> 0
  2  1 0 0 0 1 0 0 0                   2 -> 4 -> 0
  3  0 1 0 0 0 1 0 0                   3 -> 5 -> 1
  4  0 1 1 0 0 1 0 0                   4 -> 5 -> 2 -> 1
  5  0 0 0 1 1 0 0 0                   5 -> 4 -> 3
  6  0 0 0 0 0 0 0 1                   6 -> 7
  7  0 0 0 0 0 0 1 0                   7 -> 6

64 cells, 16 ones (2e)                  8 heads + 16 list nodes

Same graph, two layouts: the matrix pays for every pair; the lists pay only for real edges.

5 · Worked Examples

Example 1 Easy

A directed graph has 100 vertices and 300 edges. How many cells does an adjacency matrix use, and how many list nodes does an adjacency list use?

Solution

Matrix: 100² = 10 000 cells. Lists: 100 heads + 300 nodes (one per directed edge).

Example 2 Medium

What does this print?

#define N 8
struct node {
    int v;
    struct node *next;
};
struct node *adj[N];                      /* adjacency lists, all NULL at start */

void addEdge(int a, int b)                /* insert b at the head of a's list */
{
    struct node *p = malloc(sizeof(struct node));
    p->v = b;
    p->next = adj[a];
    adj[a] = p;
}

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    struct node *p;
    for (i = 0; i < 8; i++) {
        addEdge(e[i][0], e[i][1]);
        addEdge(e[i][1], e[i][0]);
    }
    for (i = 0; i < 6; i++) {
        printf("%d:", i);
        for (p = adj[i]; p != NULL; p = p->next) printf(" %d", p->v);
        printf("\n");
    }
    return 0;
}

Solution

Head insertion reverses the input order of each list.

Output

0: 2 1
1: 4 3 0
2: 4 0
3: 5 1
4: 5 2 1
5: 4 3

Example 3 GATE

A simple undirected graph has adjacency matrix A. What does the sum of all entries of A equal? What does the trace (diagonal sum) of A² equal?

Solution

Sum of entries = Σ deg = 2e. Trace of A² = Σ (A²)[i][i] = Σ deg(i) = 2e as well.

6 · GATE Traps

⚠️

• Undirected matrix: set both g[u][v] and g[v][u]; ones count 2e.
• Adjacency list space is Θ(n + e), matrix Θ(n²) regardless of e.
• Head insertion stores neighbours in reverse input order.
• Edge test is O(1) only in a matrix.
• Incidence matrix is n × e, not n × n.

8 · Memory Hook

🧠

“Grid for pairs, notebook for neighbours.” Matrix: Θ(n²), O(1) edge test. Lists: Θ(n + e), fast neighbour scans.

9 · Connect the Dots

Lesson 6.2 stored a graph. Questions such as “which vertices can be reached from 0?” or “how many components are there?” need a systematic visit. Next lesson answers: how do we visit every reachable vertex systematically — ring by ring, or one route at a time — and what does it cost?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markSpace

Space for an adjacency list of a graph with n vertices and e edges:

• (A) Θ(n + e)
• (B) Θ(n²)
• (C) Θ(n·e)
• (D) Θ(e²)

Q2MCQ2 marksOutput

What does this print?

#define N 8
int g[N][N];                              /* adjacency matrix, all 0 at start */

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int m = 8, i, j, deg, sum = 0;
    for (i = 0; i < m; i++) {
        g[e[i][0]][e[i][1]] = 1;          /* undirected: set both entries */
        g[e[i][1]][e[i][0]] = 1;
    }
    for (i = 0; i < N; i++) {
        deg = 0;
        for (j = 0; j < N; j++) deg += g[i][j];   /* row sum = degree */
        printf("%d ", deg);
        sum += deg;
    }
    printf("| %d\n", sum / 2);
    return 0;
}

• (A) 2 3 2 2 3 2 1 1 | 8
• (B) 2 3 2 2 3 2 1 1 | 16
• (C) 1 2 1 1 2 1 1 0 | 8
• (D) 2 3 2 2 3 2 1 1 | 4

Q3NAT1 markOnes

A simple undirected graph has 13 edges. How many 1s are in its adjacency matrix?

Numerical answer: ________

Q4NAT2 marksOutput

What does this print in its line for vertex 4?

#define N 8
struct node {
    int v;
    struct node *next;
};
struct node *adj[N];                      /* adjacency lists, all NULL at start */

void addEdge(int a, int b)                /* insert b at the head of a's list */
{
    struct node *p = malloc(sizeof(struct node));
    p->v = b;
    p->next = adj[a];
    adj[a] = p;
}

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    struct node *p;
    for (i = 0; i < 8; i++) {
        addEdge(e[i][0], e[i][1]);
        addEdge(e[i][1], e[i][0]);
    }
    for (i = 0; i < 6; i++) {
        printf("%d:", i);
        for (p = adj[i]; p != NULL; p = p->next) printf(" %d", p->v);
        printf("\n");
    }
    return 0;
}

Numerical answer: ________

Q5MSQ1 markMatrix

For the adjacency matrix A of a simple undirected graph, which are true?

• (A) (A²)[i][i] = deg(i).
• (B) The diagonal of A is all 0.
• (C) Row i sums to deg(i).
• (D) A is symmetric.

11 · Rule Card

• Matrix: n × n, Θ(n²) space, O(1) edge test, Θ(n) neighbour scan; symmetric for undirected; 2e ones.
• Lists: Θ(n + e) space; head insertion reverses input order.
• Incidence: n × e; two 1s per column (undirected).
• (A²)[i][j] = walks of length 2; diagonal = degrees.
• Dense → matrix; sparse → lists.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

adjacency matrixadjacency listincidence matrixA² counts walks of length 2

13 · Answer Vault