Graph representation

A logical graph must be stored so algorithms can iterate neighbors efficiently. Common layouts are the adjacency matrix, incidence matrix (vertex–edge), adjacency list, and edge list. This page compares them before BFS/DFS and shortest-path code.

1) Adjacency matrix

An adjacency matrix stores a graph in a two-dimensional array A of size V × V, where rows and columns correspond to vertex indices 0 … V−1.

Definition

• Unweighted: A[i][j] = 1 if there is an edge from i to j, else 0.
• Weighted: A[i][j] = w if edge (i,j) has weight w; use 0, ∞, or a sentinel (e.g. INT_MAX) for “no edge”—pick one convention and stick to it in code.
• Undirected: the matrix is symmetric: A[i][j] = A[j][i]. Self-loops appear on the diagonal.
• Directed: A[i][j] only describes the arc i → j; A[j][i] may differ.

Storage in C

With a fixed maximum V, use a 2D array and initialize for weighted graphs:

#define MAXV 500
int adj[MAXV][MAXV];   /* unweighted: 0/1 */

/* weighted: often diagonal 0, no-edge = INF */
void init_matrix(int V) {
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            adj[i][j] = (i == j) ? 0 : INF;
}

Space is Θ(V²) regardless of edge count—reasonable when V is small or the graph is dense.

Example: undirected path (4 vertices)

Edges (0,1), (1,2), (2,3) — symmetric matrix; 1 = edge.

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

Example: directed (3 vertices)

Arcs 0→1, 1→2, 0→2.

      0  1  2
   0  0  1  1
   1  0  0  1
   2  0  0  0

Degree from the matrix

• Undirected: degree of vertex i ≈ sum of row i (adjust if you allow self-loops).
• Directed: out-degree(i) = sum of row i; in-degree(i) = sum of column i.

Common operations

• Pros: Edge queries in O(1); simple code; natural input for all-pairs shortest paths (Floyd–Warshall).
• Cons: O(V²) memory; scanning neighbors always O(V) even when degree is 1.

2) Incidence matrix

An incidence matrix relates vertices to edges. Label vertices 0 … V−1 and edges e₀ … eE−1. A common shape is V × E: one row per vertex, one column per edge.

Undirected (simple graph)

Set B[v][k] = 1 if vertex v touches edge ek, else 0. Each column has exactly two ones (the two endpoints). Parallel edges get separate columns.

Example: triangle (3 vertices, 3 edges)

Vertices 0, 1, 2. Edges e₀ = (0,1), e₁ = (1,2), e₂ = (0,2).

           e₀  e₁  e₂
 vertex 0    1   0   1
 vertex 1    1   1   0
 vertex 2    0   1   1

Directed graphs

Often column k has +1 at the tail of arc k and −1 at the head (other sign conventions exist). Alternatively use two nonnegative incidence matrices (out vs in) depending on the application.

Arcs 0→1, 1→2 (e₀, e₁): tail +1, head −1.

           e₀   e₁
 vertex 0   +1    0
 vertex 1   −1   +1
 vertex 2    0   −1

Space and operations

• Space: Θ(V·E). For sparse graphs (E ≈ V) this can beat V² adjacency storage; for dense graphs (E ≈ V²) it is roughly similar order to storing the full adjacency matrix.
• Neighbor iteration: Finding edges incident on vertex v means scanning row v — O(E) unless you compress rows.
• Uses: Graph theory proofs, linear algebra on graphs (Laplacians), some circuit / network formulations—less common than adjacency lists in typical competitive-programming BFS/DFS templates.

3) Adjacency list

Keep an array of length V; each slot holds a list (linked list or dynamic array in C) of neighbors (and weights). This is the default for sparse interview graphs.

Sketch in C

typedef struct AdjNode {
    int dest;
    int weight;    /* optional */
    struct AdjNode *next;
} AdjNode;

typedef struct {
    AdjNode *head;   /* first edge from this vertex */
} GraphList[MAXV];

• Pros: Space O(V + E); iterate neighbors in O(degree(u)).
• Cons: Edge existence check may require scanning a list.

4) Edge list

Store triples (u, v) or (u, v, w) in an array or list. Minimal memory for E edges; ideal when you sort edges (e.g. Kruskal) or stream them.

Example

Directed weighted edges:
  { from, to, w }: (0,1,4), (1,2,2), (0,2,7)

5) Choosing a representation