Graph representations

ACompressed recap

🧾

An adjacency matrix uses Θ(n²) space, answers “is u–v an edge?” in O(1), and is symmetric for undirected graphs with 2e ones. Adjacency lists use Θ(n + e) space and list neighbours in Θ(deg); head insertion stores neighbours in reverse input order. An incidence matrix is n × e with two 1s per column. (A²)[i][j] counts walks of length 2.

BMerged rule card

6.2 Graph representations: adjacency matrix, adjacency list, incidence matrix

• 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.

CInterleaved GATE-style questions

Q1MCQ1 markEdge test

Checking whether u–v is an edge with an adjacency list costs:

• (A) O(deg u)
• (B) O(1)
• (C) O(n²)
• (D) O(e²)

Q2NAT2 marksCells

An incidence matrix of a graph with 7 vertices and 10 edges has how many cells?

Numerical answer: ________

Q3NAT2 marksA²

In the running example (edges 0–1, 0–2, 1–3, 1–4, 2–4, 3–5, 4–5), what is (A²)[1][2]?

Numerical answer: ________

Q4MCQ2 marksOutput

What is the line printed for vertex 1?

#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;
}

• (A) 1: 4 3
• (B) 1: 0 3 4
• (C) 1: 3 4
• (D) 1: 4 3 0

Q5MCQ1 markDense

For a dense graph (e ≈ n²) with many “is there an edge?” queries, the better choice is:

• (A) edge list sorted by weight
• (B) adjacency matrix
• (C) adjacency list
• (D) incidence matrix

Q6MSQ2 marksSpace

For a directed graph with n vertices and e edges, which are true?

• (A) The adjacency matrix has n² cells.
• (B) The adjacency lists hold e nodes in total.
• (C) The column sum of the matrix gives the out-degree.
• (D) The adjacency matrix need not be symmetric.

Q7NAT1 markMatrix sum

The sum of all entries of the adjacency matrix of a simple undirected graph is 40. How many edges?

Numerical answer: ________

Q8MCQ2 marksNeighbours

Listing all neighbours of every vertex costs, with an adjacency matrix and with adjacency lists respectively:

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

DAnswer Vault