Self-checkedTier 1 29 min readpds.graph-representations

Graph representations

How a graph is stored in memory. The adjacency matrix, the adjacency list, the edge list and the incidence matrix, with the space and the time of every common operation (is there an edge, list the neighbours, in-degree, visit all edges, transpose), the degree and edge-count facts GATE uses (handshake, maximum edges, ones in the matrix, nodes in the lists), walks counted by powers of the matrix, and the number of graphs on n labelled vertices.

Why it exists

Graphs model networks of every kind (roads, links between web pages, dependencies between tasks), and every graph algorithm starts by asking the same question: how is the graph stored? The answer changes the cost of the algorithm. Checking whether two vertices are joined, listing the neighbours of a vertex, finding who points at a vertex, and visiting every edge are cheap in one representation and expensive in the other, and GATE asks for those costs directly. This page covers the representations and their costs; the algorithms that use them (breadth-first and depth-first search, shortest paths, spanning trees) come in the Algorithms subject.

Prerequisites

Arrays and indexing Singly linked lists

Precise definitions

Graph. $G = (V, E)$ with $n = |V|$ vertices and $e = |E|$ edges. In an undirected graph an edge is an unordered pair $\{u, v\}$ ; in a directed graph (digraph) it is an ordered pair $u \to v$ . A graph is simple if it has no self-loops ( $u \to u$ ) and no parallel edges (the same edge twice). This page assumes simple graphs unless said otherwise.
Degree. In an undirected graph $\deg(v)$ is the number of edges at $v$ (a self-loop counts twice). In a digraph, the out-degree is the number of edges leaving $v$ and the in-degree the number entering it.
Handshake lemma. In an undirected graph $\sum_v \deg(v) = 2e$ , so the number of vertices of odd degree is even. In a digraph $\sum_v \text{in-degree}(v) = \sum_v \text{out-degree}(v) = e$ .
Most edges. A simple undirected graph has at most $\binom{n}{2} = n(n-1)/2$ edges; a simple digraph (no self-loops) at most $n(n-1)$ . A graph is sparse when $e = O(n)$ and dense when $e = \Theta(n^2)$ .
Adjacency matrix. An $n \times n$ array $A$ with $A[i][j] = 1$ if there is an edge $i \to j$ and 0 otherwise (for a weighted graph, the weight, with a special value for "no edge"). For an undirected graph $A$ is symmetric; for a simple graph the diagonal is 0. The row sum of row $i$ is the out-degree (the degree if undirected) and the column sum of column $j$ is the in-degree. The number of 1s is $e$ for a digraph and $2e$ for an undirected simple graph. Space $\Theta(n^2)$ , whatever $e$ is.
Adjacency list. An array of $n$ linked lists; the list of $u$ holds the vertices that $u$ points at (its neighbours). The lists contain $e$ nodes in total for a digraph and $2e$ for an undirected graph (each edge appears in two lists). Space $\Theta(n + e)$ . The order of the neighbours in a list is not fixed by the graph: it depends on how the lists were built.
Edge list. Just the $e$ pairs (plus $n$ if isolated vertices must be remembered). Space $\Theta(n + e)$ ; an edge query, the neighbours or the degree of a vertex, and visiting all the edges each scan the whole list, $\Theta(e)$ .
Incidence matrix. An $n \times e$ array: entry $(v, k)$ is 1 if vertex $v$ is an end of edge $k$ (for a directed graph usually $+1$ at the tail and $-1$ at the head). Each column of a loopless undirected graph has exactly two 1s, and the sign convention for directed graphs varies between books. Space $\Theta(ne)$ ; finding the two ends of an edge takes $\Theta(n)$ (scan its column). It is rarely used in programs.
Costs (for $n$ vertices and $e$ edges; $u$ and $v$ are given):

Operation	Adjacency matrix	Adjacency list
Space	$\Theta(n^2)$	$\Theta(n + e)$
Is there an edge $u \to v$ ?	$O(1)$	$O(\text{outdeg}(u))$
List the neighbours of $u$ (out)	$\Theta(n)$	$\Theta(\text{outdeg}(u))$
Out-degree of $u$	$\Theta(n)$ (or $O(1)$ if stored)	$\Theta(\text{outdeg}(u))$ (or $O(1)$ if stored)
In-degree of $v$ (digraph)	$\Theta(n)$ (scan a column)	$\Theta(n + e)$ (scan all lists)
Add an edge	$O(1)$	$O(1)$ at the head of the list (add the cost of a duplicate check if one is made)
Remove an edge $u \to v$	$O(1)$	$O(\text{outdeg}(u))$
Visit every edge	$\Theta(n^2)$	$\Theta(n + e)$
Transpose (reverse every edge)	$\Theta(n^2)$	$\Theta(n + e)$

So the matrix wins on edge queries and on in-degrees and in-neighbours (a column, $\Theta(n)$ , against a scan of every list), and loses on enumerating all the edges or the out-neighbours of a vertex; it also wastes space on sparse graphs. A typical rule: use the list for sparse graphs and the matrix for dense ones or when constant-time edge queries matter. A traversal (BFS or DFS) costs $\Theta(n^2)$ with a matrix and $\Theta(n + e)$ with lists.

Matrix powers count walks. For the adjacency matrix $A$ of a graph, $(A^k)_{ij}$ is the number of walks of length $k$ from $i$ to $j$ (a walk may repeat vertices and edges). In a simple undirected graph $(A^2)_{ii} = \deg(i)$ , and $\operatorname{trace}(A^3)/6$ is the number of triangles. The transpose $A^{T}$ is the matrix of the graph with every edge reversed.
Counting graphs. On $n$ labelled vertices there are $2^{\binom{n}{2}}$ simple undirected graphs and $2^{n(n-1)}$ simple digraphs; $\binom{\binom{n}{2}}{m}$ of the undirected ones have exactly $m$ edges. The numbers of connected ones for $n = 1, \ldots, 6$ are $1, 1, 4, 38, 728, 26704$ . The most edges a disconnected simple graph on $n \ge 2$ vertices can have is $\binom{n-1}{2}$ (one isolated vertex and a complete graph on the other $n - 1$ ), so every simple graph with more than $\binom{n-1}{2}$ edges is connected. Proof sketch: if the largest component has $k \le n - 1$ vertices, there are at most $\binom{k}{2} + \binom{n-k}{2}$ edges, which is largest at $k = n - 1$ .

How it works

Building both structures

One undirected graph is built edge by edge in both forms. Each add_edge(u, v) writes two cells of the matrix (the matrix is symmetric) and puts one new node at the front of each of the two lists, which is why a vertex's neighbours appear in the reverse order of their insertion. The matrix always occupies 25 cells; the lists occupy exactly as many nodes as needed.

One undirected graph, stored two ways

Real run

C source

1#include <stdlib.h>

3#define N 5

5struct node {

6 int v;

7 struct node *next;

8};

10int adj_matrix[N][N];

11struct node *adj_list[N];

13void add_edge(int u, int v) {

14 adj_matrix[u][v] = 1;

15 adj_matrix[v][u] = 1;

16 struct node *a = malloc(sizeof *a);

17 a->v = v;

18 a->next = adj_list[u];

19 adj_list[u] = a;

20 struct node *b = malloc(sizeof *b);

21 b->v = u;

22 b->next = adj_list[v];

23 adj_list[v] = b;

24}

Adjacency matrix (row = from, column = to)

	0	1	2	3	4
0	0	0	0	0	0
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	0	0
4	0	0	0	0	0

Adjacency lists (one linked list per vertex)

0→ NULL

1→ NULL

2→ NULL

3→ NULL

4→ NULL

Counts

edges completely added so far = 0, matrix cells equal to 1 = 0 (matrix always uses 25 cells), list nodes = 0

Blue = the position this step is working on, amber = a position being compared, red = positions just swapped, green = finished or in its final place, a filled blue cell = a value just placed, faded = not part of the structure at this step.

Step 1

A graph with 5 vertices (0 to 4) and no edges yet. The matrix is 5 by 5 zeros; every list is empty.

1 / 21

The five edges 0-1, 0-2, 1-2, 1-3 and 3-4 are added by hidden driver code, one add_edge() call each. add_edge() is the exact code that runs. The matrix and every list are read from the program's memory after each step. New list nodes are put at the front of a list, so neighbours appear in reverse order of insertion. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1One directed graph, both representations, and its degrees

Easy

#include <stdio.h>
#include <stdlib.h>
 
#define N 5
 
struct node {
    int v;
    struct node *next;
};
 
static int matrix[N][N];
static struct node *adj[N];
 
/* directed edge u -> v, added at the end of u's list so that lists keep the input order */
static void add_edge(int u, int v) {
    matrix[u][v] = 1;
    struct node *p = malloc(sizeof *p);
    if (p == NULL) exit(1);
    p->v = v;
    p->next = NULL;
    struct node **pp = &adj[u];
    while (*pp != NULL) pp = &(*pp)->next;
    *pp = p;
}
 
int main(void) {
    int edges[7][2] = {{0, 1}, {0, 2}, {1, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 0}};
    for (int k = 0; k < 7; k++) add_edge(edges[k][0], edges[k][1]);
 
    printf("matrix (row = from, column = to):\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) printf("%d ", matrix[i][j]);
        printf("\n");
    }
    printf("lists:\n");
    for (int i = 0; i < N; i++) {
        printf("%d:", i);
        for (struct node *p = adj[i]; p != NULL; p = p->next) printf(" %d", p->v);
        printf("\n");
    }
    printf("vertex out-degree (row sum, list length) in-degree (column sum)\n");
    for (int i = 0; i < N; i++) {
        int row = 0, col = 0, len = 0;
        for (int j = 0; j < N; j++) {
            row += matrix[i][j];
            col += matrix[j][i];
        }
        for (struct node *p = adj[i]; p != NULL; p = p->next) len++;
        printf("%6d %10d %10d %20d\n", i, row, len, col);
    }
    return 0;
}

Output:

matrix (row = from, column = to):
0 1 1 0 0
0 0 1 0 0
0 0 0 1 0
0 1 0 0 1
1 0 0 0 0
lists:
0: 1 2
1: 2
2: 3
3: 1 4
4: 0
vertex out-degree (row sum, list length) in-degree (column sum)
     0          2          2                    1
     1          1          1                    2
     2          1          1                    2
     3          2          2                    1
     4          1          1                    1

Reading it. The seven directed edges are $0 \to 1$ , $0 \to 2$ , $1 \to 2$ , $2 \to 3$ , $3 \to 1$ , $3 \to 4$ and $4 \to 0$ . In the matrix the 1s are the edges, so there are seven of them (row $i$ , column $j$ means $i \to j$ ). The lists show the same information: the list of 3 holds 1 and 4. The row sums are the out-degrees and equal the list lengths. The column sums are the in-degrees; they are not visible in the lists without scanning all of them (for example vertex 1 is in the lists of 0 and 3, so its in-degree is 2). The out-degrees add up to 7 and so do the in-degrees: the directed handshake lemma.

EX 2What the operations cost, measured

Medium

#include <stdio.h>
#include <stdlib.h>
 
#define N 1000
#define E 5000
 
struct node {
    int v;
    struct node *next;
};
 
static unsigned char matrix[N][N];
static struct node *adj[N];
 
static unsigned rnd(void) {
    static unsigned s = 99;
    s = s * 1103515245u + 12345u;
    return s >> 8;
}
 
int main(void) {
    int added = 0;
    while (added < E) {
        int u = (int)(rnd() % N), v = (int)(rnd() % N);
        if (u == v || matrix[u][v]) continue;
        matrix[u][v] = 1;
        struct node *p = malloc(sizeof *p);
        if (p == NULL) return 1;
        p->v = v;
        p->next = adj[u];
        adj[u] = p;
        added++;
    }
    int u = 17, v = 523;
    long steps;
 
    printf("directed graph, n = %d, e = %d (steps = cells or list nodes looked at)\n", N, E);
 
    /* is there an edge u -> w ?  one absent and one present query */
    int present = adj[u]->next->v; /* the second node of u's list is certainly an edge */
    int queries[2] = {v, present};
    for (int q = 0; q < 2; q++) {
        int w = queries[q];
        steps = 1;
        int found_m = matrix[u][w];
        long steps_l = 0;
        int found_l = 0;
        for (struct node *p = adj[u]; p != NULL; p = p->next) {
            steps_l++;
            if (p->v == w) { found_l = 1; break; }
        }
        printf("edge %d -> %3d exists? %-3s  matrix: %4ld step   list: %4ld steps (answers agree: %s)\n", u, w, found_m ? "yes" : "no", steps, steps_l, found_m == found_l ? "yes" : "no");
    }
 
    /* out-neighbours of u */
    steps = 0;
    int out_m = 0;
    for (int j = 0; j < N; j++) {
        steps++;
        out_m += matrix[u][j];
    }
    long steps_l = 0;
    int out_l = 0;
    for (struct node *p = adj[u]; p != NULL; p = p->next) {
        steps_l++;
        out_l++;
    }
    printf("out-neighbours of %d (%d of them): matrix: %4ld steps  list: %4ld steps (agree: %s)\n", u, out_m, steps, steps_l, out_m == out_l ? "yes" : "no");
 
    /* in-degree of v */
    steps = 0;
    int indeg_m = 0;
    for (int i = 0; i < N; i++) {
        steps++;
        indeg_m += matrix[i][v];
    }
    steps_l = 0;
    int indeg_l = 0;
    for (int i = 0; i < N; i++) {
        steps_l++;
        for (struct node *p = adj[i]; p != NULL; p = p->next) {
            steps_l++;
            if (p->v == v) indeg_l++;
        }
    }
    printf("in-degree of %d:            matrix: %6ld steps  list: %6ld steps (both give %d: %s)\n", v, steps, steps_l, indeg_m, indeg_m == indeg_l ? "yes" : "no");
 
    /* list all edges */
    steps = 0;
    long count_m = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            steps++;
            count_m += matrix[i][j];
        }
    steps_l = 0;
    long count_l = 0;
    for (int i = 0; i < N; i++) {
        steps_l++;
        for (struct node *p = adj[i]; p != NULL; p = p->next) {
            steps_l++;
            count_l++;
        }
    }
    printf("list all edges:            matrix: %6ld steps  list: %6ld steps (both find %ld: %s)\n", steps, steps_l, count_m, count_m == count_l ? "yes" : "no");
    return 0;
}

Output:

directed graph, n = 1000, e = 5000 (steps = cells or list nodes looked at)
edge 17 -> 523 exists? no   matrix:    1 step   list:    5 steps (answers agree: yes)
edge 17 -> 111 exists? yes  matrix:    1 step   list:    2 steps (answers agree: yes)
out-neighbours of 17 (5 of them): matrix: 1000 steps  list:    5 steps (agree: yes)
in-degree of 523:            matrix:   1000 steps  list:   6000 steps (both give 6: yes)
list all edges:            matrix: 1000000 steps  list:   6000 steps (both find 5000: yes)

Reading it. A random directed graph with 1000 vertices and 5000 edges is stored both ways, and each line counts the matrix cells or list nodes looked at (both counts come from loops that really read the cells and the nodes). Vertex 17 has out-degree 5. Asking about an edge that is absent costs 1 step with the matrix and, with the list, a scan of the whole list: 5 steps, the out-degree. Asking about an edge that is present stops as soon as it is found: 2 steps here, because it is the second node. Listing the out-neighbours of a vertex costs the whole row, 1000 steps, with the matrix, but only the out-degree (5) with the list. The in-degree of a vertex needs a column of the matrix (1000 steps) but a scan of all the lists with the list representation (1000 list heads plus 5000 nodes = 6000 steps, which is $n + e$ ). Listing every edge scans a million cells but only 6000 list positions. These are the entries of the cost table in action.

EX 3Powers of the adjacency matrix: walks and triangles

GATE level

#include <stdio.h>
 
#define N 5
 
int main(void) {
    int a[N][N] = {{0}};
    int edges[5][2] = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}};
    for (int k = 0; k < 5; k++) {
        a[edges[k][0]][edges[k][1]] = 1;
        a[edges[k][1]][edges[k][0]] = 1;
    }
    int a2[N][N] = {{0}}, a3[N][N] = {{0}};
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++) a2[i][j] += a[i][k] * a[k][j];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++) a3[i][j] += a2[i][k] * a[k][j];
    printf("A squared (entry = number of walks of length 2):\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) printf("%d ", a2[i][j]);
        printf("\n");
    }
    int trace = 0;
    for (int i = 0; i < N; i++) trace += a3[i][i];
    printf("diagonal of A squared (the degrees): ");
    for (int i = 0; i < N; i++) printf("%d ", a2[i][i]);
    printf("\ntrace of A cubed = %d, so triangles = %d\n", trace, trace / 6);
    printf("walks of length 3 from 0 to 4: %d\n", a3[0][4]);
    return 0;
}

Output:

A squared (entry = number of walks of length 2):
2 1 1 1 0
1 3 1 0 1
1 1 2 1 0
1 0 1 2 0
0 1 0 0 1
diagonal of A squared (the degrees): 2 3 2 2 1
trace of A cubed = 6, so triangles = 1
walks of length 3 from 0 to 4: 1

Reading it. The graph has the edges $0\text{-}1$ , $0\text{-}2$ , $1\text{-}2$ , $1\text{-}3$ , $3\text{-}4$ . The diagonal of $A^2$ is the degree sequence $2, 3, 2, 2, 1$ , because $(A^2)_{ii}$ counts the walks of length 2 that leave $i$ and come back, one for each neighbour. An off-diagonal entry such as $(A^2)_{01} = 1$ says there is one walk of length 2 from 0 to 1, namely $0 \to 2 \to 1$ . The trace of $A^3$ is 6, and every triangle gives 6 closed walks of length 3 (3 starting vertices times 2 directions), so there is $6/6 = 1$ triangle (the vertices 0, 1, 2). The entry $(A^3)_{04} = 1$ is the single walk $0 \to 1 \to 3 \to 4$ . Note that these count walks, not paths: walks may revisit vertices.

EX 4When is the list smaller than the matrix?

Medium

#include <stdio.h>
 
struct node {
    int v;
    struct node *next;
};
 
int main(void) {
    long n = 1000;
    long matrix_bytes = n * n * (long)sizeof(int);
    printf("sizeof(int) = %zu, sizeof(struct node) = %zu, sizeof(pointer) = %zu\n", sizeof(int), sizeof(struct node), sizeof(struct node *));
    printf("n = %ld: int matrix = %ld bytes\n", n, matrix_bytes);
    long edges[4] = {2000, 5000, 100000, 400000};
    for (int k = 0; k < 4; k++) {
        long e = edges[k];
        long list_bytes = n * (long)sizeof(struct node *) + 2 * e * (long)sizeof(struct node);
        printf("undirected, e = %6ld: lists = %8ld bytes (%s than the matrix)\n", e, list_bytes, list_bytes < matrix_bytes ? "smaller" : "larger");
    }
    long best = 0;
    for (long e = 0; e <= n * (n - 1) / 2; e++) {
        long list_bytes = n * (long)sizeof(struct node *) + 2 * e * (long)sizeof(struct node);
        if (list_bytes < matrix_bytes) best = e;
    }
    printf("lists stay smaller up to e = %ld edges (the graph has at most %ld possible edges)\n", best, n * (n - 1) / 2);
    return 0;
}

Output:

sizeof(int) = 4, sizeof(struct node) = 16, sizeof(pointer) = 8
n = 1000: int matrix = 4000000 bytes
undirected, e =   2000: lists =    72000 bytes (smaller than the matrix)
undirected, e =   5000: lists =   168000 bytes (smaller than the matrix)
undirected, e = 100000: lists =  3208000 bytes (smaller than the matrix)
undirected, e = 400000: lists = 12808000 bytes (larger than the matrix)
lists stay smaller up to e = 124749 edges (the graph has at most 499500 possible edges)

Reading it. For $n = 1000$ an int matrix takes $n^2 = 4{,}000{,}000$ bytes, whatever the graph. A list node of this program takes 16 bytes (an int and a pointer, with padding) and there are $2e$ of them for an undirected graph, plus $n$ head pointers of 8 bytes. So the lists are smaller as long as $8n + 32e < 4n^2$ , that is, up to $e = 124{,}749$ edges, about a quarter of the 499,500 possible edges, if a node costs exactly its 16 bytes (a real malloc adds a per-block overhead, so the true break-even is lower). For $e = 400{,}000$ the lists are about 3.2 times larger than the matrix. The break-even point depends on the sizes of the types: a matrix of single bits (125,000 bytes) is 32 times smaller than this one, and the lists would win only below about $e = 3{,}656$ . The general lesson is the shape of the comparison, $\Theta(n + e)$ against $\Theta(n^2)$ : the list wins for sparse graphs, and for dense graphs the matrix is no worse in the order of growth and wastes less on pointers.

EX 5Reversing every edge (the transpose)

Medium

#include <stdio.h>
#include <stdlib.h>
 
#define N 5
 
struct node {
    int v;
    struct node *next;
};
 
static void add(struct node *adj[], int u, int v) {
    struct node *p = malloc(sizeof *p);
    if (p == NULL) exit(1);
    p->v = v;
    p->next = NULL;
    struct node **pp = &adj[u];
    while (*pp != NULL) pp = &(*pp)->next;
    *pp = p;
}
 
/* insert at the front of the list: O(1) */
static void add_front(struct node *adj[], int u, int v) {
    struct node *p = malloc(sizeof *p);
    if (p == NULL) exit(1);
    p->v = v;
    p->next = adj[u];
    adj[u] = p;
}
 
static void show(const char *name, struct node *adj[]) {
    printf("%s\n", name);
    for (int i = 0; i < N; i++) {
        printf("  %d:", i);
        for (struct node *p = adj[i]; p != NULL; p = p->next) printf(" %d", p->v);
        printf("\n");
    }
}
 
int main(void) {
    struct node *g[N] = {NULL}, *t[N] = {NULL};
    int edges[7][2] = {{0, 1}, {0, 2}, {1, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 0}};
    int m[N][N] = {{0}}, mt[N][N] = {{0}};
    for (int k = 0; k < 7; k++) {
        add(g, edges[k][0], edges[k][1]);
        m[edges[k][0]][edges[k][1]] = 1;
    }
    /* transpose with lists: visit every edge u -> v once and add v -> u at the front of its list: n + e steps */
    for (int u = 0; u < N; u++)
        for (struct node *p = g[u]; p != NULL; p = p->next) add_front(t, p->v, u);
    /* transpose with a matrix: n * n cells */
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) mt[j][i] = m[i][j];
    show("graph", g);
    show("transpose (every edge reversed)", t);
    int same = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int found = 0;
            for (struct node *p = t[i]; p != NULL; p = p->next)
                if (p->v == j) found = 1;
            if (found != mt[i][j]) same = 0;
        }
    }
    printf("list transpose agrees with the matrix transpose: %s\n", same ? "yes" : "no");
    return 0;
}

Output:

graph
  0: 1 2
  1: 2
  2: 3
  3: 1 4
  4: 0
transpose (every edge reversed)
  0: 4
  1: 3 0
  2: 1 0
  3: 2
  4: 3
list transpose agrees with the matrix transpose: yes

Reading it. The transpose graph has an edge $v \to u$ for every edge $u \to v$ . With lists this is one pass over all the nodes of all the lists, adding $u$ at the front of the list of $v$ each time (a constant-time step, so $\Theta(n + e)$ in all; appending at the tail by walking the list each time would make it slower, up to quadratic for a vertex that many edges point at). With the matrix it is $\Theta(n^2)$ (the matrix $A^T$ ). The program builds the reversed lists, and also the transposed matrix, and checks that they describe the same edges. In the transposed graph the list of 1 holds 3 and 0 (front insertion reverses the order), which are exactly the vertices that pointed at 1: reversing the edges turns the in-neighbours of a vertex into its out-neighbours. This is how an algorithm that needs in-neighbours (such as finding strongly connected components) gets them cheaply from a list representation.

EX 6Counting graphs, and the connectivity bound

GATE level

#include <stdio.h>
 
static int connected(int n, int mask, int pair_u[], int pair_v[], int pairs) {
    int seen = 1, changed = 1;
    while (changed) {
        changed = 0;
        for (int k = 0; k < pairs; k++) {
            if (!((mask >> k) & 1)) continue;
            int a = (seen >> pair_u[k]) & 1, b = (seen >> pair_v[k]) & 1;
            if (a != b) {
                seen |= (1 << pair_u[k]) | (1 << pair_v[k]);
                changed = 1;
            }
        }
    }
    return seen == (1 << n) - 1;
}
 
int main(void) {
    printf("n  labelled graphs  connected  most edges in a disconnected graph  (n-1)(n-2)/2\n");
    for (int n = 2; n <= 6; n++) {
        int pu[15], pv[15], pairs = 0;
        for (int u = 0; u < n; u++)
            for (int v = u + 1; v < n; v++) {
                pu[pairs] = u;
                pv[pairs] = v;
                pairs++;
            }
        long total = 1L << pairs, conn = 0;
        int most_disconnected = -1;
        for (int mask = 0; mask < total; mask++) {
            int e = __builtin_popcount((unsigned)mask);
            if (connected(n, mask, pu, pv, pairs)) conn++;
            else if (e > most_disconnected) most_disconnected = e;
        }
        printf("%d  %15ld  %9ld  %34d  %13d\n", n, total, conn, most_disconnected, (n - 1) * (n - 2) / 2);
    }
    return 0;
}

Output:

n  labelled graphs  connected  most edges in a disconnected graph  (n-1)(n-2)/2
2                2          1                                   0              0
3                8          4                                   1              1
4               64         38                                   3              3
5             1024        728                                   6              6
6            32768      26704                                  10             10

Reading it. The program tries every set of edges on $n$ labelled vertices. The number of graphs is $2^{\binom{n}{2}}$ (each of the $\binom{n}{2}$ possible edges is present or absent): $2, 8, 64, 1024, 32768$ for $n = 2, \ldots, 6$ . The number of connected ones (for $n = 2, \ldots, 6$ ; for $n = 1$ both counts are 1) is $1, 4, 38, 728, 26704$ . The fourth column is the largest number of edges of any disconnected graph, and it equals $(n-1)(n-2)/2 = \binom{n-1}{2}$ every time: isolate one vertex and join all the others. So a simple graph on $n$ vertices with more than $\binom{n-1}{2}$ edges must be connected. For $n = 6$ any graph with 11 or more edges is connected, while a disconnected graph with 10 edges exists. The count of graphs with exactly $m$ edges is a binomial coefficient: for $n = 4$ it is $\binom{6}{m} = 1, 6, 15, 20, 15, 6, 1$ for $m = 0, \ldots, 6$ .

EX 7Counting ones and list nodes

Easy

An undirected simple graph has 8 vertices and 12 edges.

Quantity	Value	Why
Sum of the degrees	24	handshake: $2e$
Ones in the adjacency matrix	24	each edge sets two cells, and the diagonal is 0
Nodes in all the adjacency lists	24	each edge is in two lists
Cells in the matrix	64	always $n^2$
Average degree	3	$2e/n = 24/8$
Most edges possible	28	$\binom{8}{2}$

For a directed graph with the same $n$ and $e$ the matrix has 12 ones, the lists have 12 nodes, the sum of out-degrees is 12 and the sum of in-degrees is 12, and at most $8 \cdot 7 = 56$ edges are possible.

Reading it. Everything follows from "an undirected edge is stored twice, a directed edge once". The question "how many nodes are in the adjacency lists" is the same as "what is the sum of the degrees" for an undirected graph and the same as "how many edges" for a directed one.

EX 8Which representation for which job?

GATE level

For each situation, choose the better representation and say why.

Situation	Choice	Reason
A road network with $10^6$ junctions and $3 \cdot 10^6$ road segments	adjacency list	the matrix would need $10^{12}$ cells (terabytes with an `int` per cell, about 125 gigabytes even with one bit per cell); the list needs $\Theta(n + e)$
A graph on 200 vertices in which almost every pair is joined, with many "is there an edge?" queries	adjacency matrix	dense, and each query is $O(1)$
An algorithm that visits every neighbour of every vertex once (BFS or DFS) on a sparse graph	adjacency list	$\Theta(n + e)$ instead of $\Theta(n^2)$
An algorithm that needs the in-degree of every vertex of a digraph	adjacency list	one pass over all the edges, $\Theta(n + e)$ , which is the same cost as one in-degree alone; the matrix needs $\Theta(n^2)$ (one column per vertex), equal only for dense graphs
Repeated "is $u$ adjacent to $v$ ?" on a sparse graph where space matters	plain list if $O(\text{outdeg}(u))$ is acceptable; if queries dominate, keep each neighbour set as a hash set or a sorted array (binary search, $O(\log \text{outdeg})$ )	the space stays $\Theta(n + e)$ , and a sorted linked list would not help because it is still scanned linearly

Reading it. The decision is made by the operation counts of the cost table and by whether $e$ is close to $n^2$ . For a sparse graph the matrix is dominated on space and on enumeration, and its only advantage, the $O(1)$ edge query, rarely outweighs that.

Cheat box

Matrix: $\Theta(n^2)$ space, edge query $O(1)$ , neighbours $\Theta(n)$ , in-degree $\Theta(n)$ , visit all edges $\Theta(n^2)$ . Symmetric if undirected, zero diagonal if simple.
List: $\Theta(n + e)$ space, edge query $O(\text{outdeg}(u))$ , neighbours $\Theta(\text{outdeg}(u))$ , in-degree $\Theta(n + e)$ , visit all edges $\Theta(n + e)$ . BFS and DFS: $\Theta(n + e)$ with lists, $\Theta(n^2)$ with a matrix.
Undirected edge stored twice (2 matrix 1s, 2 list nodes); directed edge once.
$\sum \deg = 2e$ . Directed: $\sum \text{in} = \sum \text{out} = e$ . Row sum = out-degree, column sum = in-degree.
At most $n(n-1)/2$ edges (undirected), $n(n-1)$ (directed), simple graphs.
$(A^k)_{ij}$ = walks of length $k$ from $i$ to $j$ . Simple undirected: $(A^2)_{ii} = \deg(i)$ and $\operatorname{trace}(A^3)/6$ = triangles. $A^T$ = reversed graph.
Labelled simple graphs: $2^{n(n-1)/2}$ undirected, $2^{n(n-1)}$ directed. More than $\binom{n-1}{2}$ edges $\Rightarrow$ connected.

Traps and GATE patterns

Connections

Builds on

Arrays and indexing Singly linked lists

Unlocks

BFS and DFSPrerequisite of BFS and DFSuses DFS edge types, topological sort and SCCuses

Across subjects

BFS and DFSuses Dijkstra's algorithmuses

Graph connectivity and treesusesplanned

Within this subject

Arrays and indexingimplemented-by Singly linked listsimplemented-by Multidimensional arrays and address calculationuses Binary heaps and heap operationsuses

The matrix is a two-dimensional array (compare the address calculation of its cells) and the lists are linked lists. Both are used by BFS and DFS, whose running times of $\Theta(n + e)$ and $\Theta(n^2)$ come from the table above, and by Dijkstra's algorithm, which combines adjacency lists with a priority queue (binary heap). The theory of connectivity, degrees and walks is in the Discrete Mathematics subject (graph connectivity).

PYQs

1 previous year question from your book. I re-solved each one myself (0 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2016 · Set 2 · MCQ · 2 marksQ11 · page 138 of the book

In an adjacency list representation of an
undirected simple graph G = (V,E), each edge
(u,v) has two adjacency list entries: [v] in the
adjacency list of u, and [u] in the adjacency list of
v. These are called twins of each other. A twin
pointer is a pointer from an adjacency list entry to
its twin. If |E|=m and |V|=n, and the memory size
is not a constraint, what is the Time Complexity
of the most efficient algorithm to set the twin
pointer in each entry in each adjacency list?

(a)θ (n2)
(b)θ (n+m)
(c)θ (m2)
(d)θ (n4)

Self-check

Question 1

An undirected simple graph has 10 vertices and 15 edges. How many 1s does its adjacency matrix have, how many nodes do its adjacency lists have, and what is the sum of the degrees?

Show answer

All three are $2e = 30$ : each edge sets two cells, appears in two lists, and adds 2 to the sum of degrees.

Question 2

State the time to find the in-degree of one given vertex of a directed graph with $n$ vertices and $e$ edges, for the adjacency matrix and for the adjacency lists.

Show answer

Matrix: $\Theta(n)$ (sum one column). Lists: $\Theta(n + e)$ (look at every list and count the nodes holding that vertex).

Question 3

What is the maximum number of edges in a simple directed graph on $n$ vertices, and how many of them can an undirected simple graph on $n$ vertices have?

Show answer

Directed: $n(n-1)$ . Undirected: $n(n-1)/2$ .

Question 4

For the adjacency matrix $A$ of a simple undirected graph, $\operatorname{trace}(A^3) = 18$ . How many triangles does the graph have?

Show answer

$18 / 6 = 3$ triangles.

Question 5

What is the maximum number of edges a disconnected simple graph on 10 vertices can have, and what does it imply for a graph with 37 edges?

Show answer

$\binom{9}{2} = 36$ . So a simple graph on 10 vertices with 37 edges (or more) must be connected.

Revision card

One-screen revision

Matrix $n \times n$ , $\Theta(n^2)$ ; edge query $O(1)$ ; neighbours and in-degree $\Theta(n)$ ; all edges $\Theta(n^2)$ .
List $\Theta(n + e)$ ; edge query $O(\deg)$ ; neighbours $\Theta(\deg)$ ; in-degree $\Theta(n + e)$ ; all edges and traversal $\Theta(n + e)$ .
Undirected: edge stored twice, $2e$ ones, $2e$ list nodes, $\sum \deg = 2e$ . Directed: $e$ , $e$ .
Max edges $n(n-1)/2$ or $n(n-1)$ . Sparse: list. Dense or many edge queries: matrix.
$(A^k)_{ij}$ = walks; simple undirected: diagonal of $A^2$ = degrees, trace $(A^3)/6$ = triangles; $A^T$ = reversed graph.
$2^{n(n-1)/2}$ labelled graphs; more than $\binom{n-1}{2}$ edges forces connectivity. List order is not canonical.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 22.1 Representations of graphs

Verification

The animation replays a real run of the shown add_edge() function: the matrix and every adjacency list are read from the running program's memory after each step, and the test suite checks that the final matrix is symmetric with ten 1s and that every list agrees with its matrix row. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c. The counting facts were checked by scripts/enum-checks/graphs.py (all graphs on up to 6 labelled vertices: the number of graphs, the number of connected ones, the handshake sum, the largest number of edges of a disconnected graph (also run by one of the programs on this page), hence that a graph with more than C(n-1, 2) edges is connected; and random graphs for the matrix power facts: walks counted by powers of the matrix, the diagonal of A squared and the trace of A cubed). The step counts in the cost example are from one run on one random graph and are examples of the growth rates, not constants. Struct and pointer sizes are those of a typical 64-bit Linux machine. The textbook section number was written from memory and has NOT been checked against the book. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Stack applications: expression evaluation and matching

AVL trees and rotations