Graph Representation: Adjacency Matrix

Math for CS · Axiom Academy

Representing graphs with matrices For a weighted graph , we store the edge weight instead of 1, and use or 0 for non-edges (depending on context). Consider a graph with 4 vertices and edges . Row i encodes the out-edges of vertex i . Column j encodes the in-edges of vertex j . The matrix is not symmetric for directed graphs. Reading Information from the Matrix Edge check: Is there an edge from u to v ? Just look at A[u][v] . Time: O(1) . Degree (undirected): Sum of row i gives . Out-degree (directed): Sum of row i : . In-degree (directed): Sum of column j : . Neighbors of v : Scan row v for non-zero entries. Time: O(n) . Powers of the Adjacency Matrix One of the most elegant properties of adjacency matrices involves matrix powers. This is useful for checking reachability, counting triangles, and analyzing network structure. The entry A^2[i][i] counts closed walks of length 2 from i back to i , which equals . Each triangle is counted 6 times (3 starting vertices, 2 directions), hence dividing by 6. O(n^2) always, regardless of how many edges exist. For sparse graphs ( ), this wastes significant memory. O(1) — direct array lookup. This is the adjacency matrix's greatest strength. O(n) — must scan the entire row. Slow for sparse graphs where the vertex may only have a few neighbors. When to Use an Adjacency Matrix The graph is dense ( m close to n^2 ) You need fast edge lookups — O(1) per query You want to compute matrix powers (walks, reachability)

This is the written version of the interactive lesson above. See the full Math for CS course.