Graph representation

Overview

A graph models things (vertices) and the connections between them (edges). The simplest computer representation is the adjacency matrix — a square grid of 0s and 1s where the cell at row i, column j says whether an edge runs from vertex i to vertex j. Everything about a vertex is then a row (its outgoing edges) or a column (its incoming edges).

Why it matters

Graphs are everywhere: road maps, social networks, package dependencies, web links, state machines, computer networks. Before you can run any algorithm on a graph you must decide how to store it, and the adjacency matrix — simple, O(1) edge lookup, ideal for dense graphs — is the representation every later algorithm in this track builds on.

Core concepts

Directed vs undirected. A directed edge i→j sets only adj[i*n+j]; an undirected edge sets both adj[i*n+j] and adj[j*n+i] (a symmetric matrix).

Out-degree of v = sum of row v. In-degree of v = sum of column v.

Edge count. For a directed graph it is the sum of all cells; for an undirected graph that sum is twice the number of edges.

Trade-off. A matrix uses n² memory regardless of how many edges exist — great for dense graphs, wasteful for sparse ones (where adjacency lists win).

Syntax notes

#define IDX(i,j,n) ((i)*(n) + (j))   /* flattened 2-D indexing */

int n = 4;
int adj[16] = { 0,1,1,0,   /* row 0: edges 0->1, 0->2 */
                0,0,1,0,
                0,0,0,1,
                0,0,0,0 };

int has_edge = adj[IDX(0,1,n)];          /* is there an edge 0 -> 1? */

int out = 0, in = 0;
for (int j = 0; j < n; j++) out += adj[IDX(v,j,n)];   /* ROW    = outgoing */
for (int i = 0; i < n; i++) in  += adj[IDX(i,v,n)];   /* COLUMN = incoming */

/* undirected: set BOTH directions */
adj[IDX(a,b,n)] = adj[IDX(b,a,n)] = 1;

Key points:

• Row v is what leaves v; column v is what arrives at v. Confusing the two is the most common beginner error.
• A flattened array indexed i*n + j is the usual C representation; the stride is always n.
• An undirected edge is two matrix entries, kept in sync.

Lesson

A graph is a set of vertices joined by edges. The workhorse representation here is the adjacency matrix: an n×n array where adj[i*n+j]==1 marks an edge i→j. Row i holds i's outgoing edges (out-degree = row sum) and column j holds j's incoming edges (in-degree = column sum). Directed graphs use the raw matrix; undirected graphs keep it symmetric.

Code examples

#include <stdio.h> /* Directed graph as an adjacency matrix: adj[in+j]==1 means edge i->j. / int main(void){ int n=4; int adj[16]={ 0,1,1,0, 0,0,1,0, 0,0,0,1, 0,0,0,0 }; int edges=0; for(int i=0;i<nn;i++) edges+=adj[i]; printf("vertices=%d edges=%d\n", n, edges); for(int v=0;v<n;v++){ int out=0,in=0; for(int j=0;j<n;j++) out+=adj[vn+j]; /* row v = outgoing / for(int i=0;i<n;i++) in +=adj[in+v]; /* col v = incoming */ printf("vertex %d: out-degree=%d in-degree=%d\n", v, out, in); } return 0; }

Line by line

Common mistakes

Confusing rows and columns: row v is out-going, column v is in-coming. Dividing a directed edge count by 2 (that correction is only for undirected graphs). Assuming the matrix is symmetric when the graph is directed.

Debugging tips

Compiler errors and warnings:

• warning: array subscript is above array bounds — your index arithmetic exceeded n*n, usually a wrong stride.
• -Wsign-compare when mixing int vertex indices with a size_t size.

Runtime symptoms:

• In-degree and out-degree are swapped. You summed the wrong direction: row is outgoing, column is incoming.
• An undirected graph behaves as one-way. You set only adj[a][b]; undirected needs both entries.
• Garbage values from a valid-looking index. The stride is wrong — with an n x n matrix every index must be i*n + j, and reusing a stride from a different matrix reads the wrong cell without crashing.
• Edge count is double what you expect. For an undirected graph the cell sum counts each edge twice; divide by 2.
• Self-loops appear unexpectedly. Check whether adj[v][v] is meant to be 0; many algorithms assume no self-loops.

Technique: print the matrix as a grid of 0s and 1s for a small graph. Symmetry (or its absence) is instantly visible, and so is a misplaced edge.

Memory safety

• Allocation size. A dynamically allocated matrix needs n * n elements; compute in size_t because n * n can overflow int for large n, producing an under-allocated buffer that is then written past.
• Validate vertex indices. Every access assumes 0 <= i, j < n. An index arriving from input must be checked; adj[i*n + j] with an out-of-range i reads or writes far outside the array without any fault on many systems.
• Stride discipline. The single most dangerous silent bug: using a stride other than n still lands inside the allocation, so nothing crashes and the results are simply wrong.
• Memory cost. The matrix uses n^2 storage regardless of edge count — 10,000 vertices means 100 million entries. For sparse graphs an adjacency list is the right structure; know when the matrix stops being appropriate.
• Initialisation. Use calloc (or memset) so absent edges are genuinely 0; malloc leaves indeterminate values that read as arbitrary edges.

Real-world uses

Concrete uses: Road and transit networks, social graphs, package-dependency graphs, web link structures, state machines, and network topologies are all graphs. The adjacency matrix specifically suits dense graphs and any algorithm that asks "is there an edge between these two?" repeatedly, since that query is O(1). Matrix representations also connect directly to linear algebra — powers of the adjacency matrix count walks of a given length.

Professional best practices:

Beginner:

• Write an IDX(i,j,n) macro or a small accessor function rather than repeating the arithmetic.
• Say out loud whether the graph is directed before you build it.

Intermediate:

• Choose the representation from density: a matrix costs n^2 memory but gives O(1) edge tests; an adjacency list costs O(V+E) and iterates neighbours faster — most real-world graphs are sparse and want lists.
• Keep n next to the matrix (in a struct) so the stride can never drift from the data.
• Decide and document your convention for self-loops and for weighted 0 entries before writing algorithms on top.

Practice tasks

1. (Beginner) Degrees. Given a flattened matrix, implement int out_degree(const int *adj, int n, int v) and int in_degree(...). Example: for the demo graph, vertex 2 has out-degree 1 and in-degree 2. Concepts: row vs column.

2. (Beginner) Build an undirected graph. Write void add_edge(int *adj, int n, int a, int b) that keeps the matrix symmetric, and verify with a printout. Concepts: symmetry, both entries.

3. (Intermediate) Count edges correctly. Implement edge counting for both directed and undirected graphs (the latter dividing by 2), and validate against a hand-built example. Concepts: representation semantics.

4. (Intermediate) Matrix vs list. Estimate the memory used by a matrix and by an adjacency list for 10,000 vertices with 30,000 edges. Concepts: choosing a representation from density.

Summary

A graph is vertices plus edges, and the adjacency matrix stores it as an n x n grid where adj[i*n + j] marks an edge from i to j. Row v holds everything leaving v (out-degree is the row sum) and column v holds everything arriving (in-degree is the column sum) — swapping the two is the classic first mistake. An undirected edge is two symmetric entries that must be kept in sync, and the total of all cells counts directed edges (twice the count for undirected). The matrix costs n^2 memory whatever the edge count, which is why it suits dense graphs and O(1) edge tests, while sparse graphs are better served by adjacency lists.

Practice with these exercises

• Out-degree of a vertex
• Count directed edges