Adjacency Matrix Representation

A graph is one of the most versatile data structures in computer science, capable of modelling everything from social networks and road maps to compiler dependency trees and neural connections. To work with graphs algorithmically, we first need a concrete way to store them in memory. One of the oldest and most intuitive representations is the adjacency matrix — a two-dimensional grid that encodes every possible relationship between every pair of vertices in a single, uniform structure. Understanding the adjacency matrix deeply means understanding not just how it is built, but why it behaves the way it does, when it excels, and when it falls short.

An adjacency matrix for a graph with V vertices is a square matrix of dimensions V × V. Each row and each column correspond to a specific vertex. The cell at row i and column j — written matrix[i][j] — records whether an edge exists from vertex i to vertex j. In the simplest case, the value is a boolean: 1 (or true) if the edge exists, and 0 (or false) if it does not. Because rows and columns are indexed directly by vertex identifiers, finding out whether two specific vertices are connected requires nothing more than a single array lookup — no searching, no traversal.

Consider a small unweighted graph with four vertices labelled 0, 1, 2, and 3, and the following edges: (0→1), (0→2), (1→3), (2→3). Its adjacency matrix looks like this:

Reading row 0 immediately reveals that vertex 0 has outgoing edges to vertices 1 and 2. Reading column 3 reveals that vertices 1 and 2 have incoming edges to vertex 3. The entire connectivity picture of the graph is contained in this flat, rectangular structure.

For weighted graphs, the binary 0/1 convention is replaced by the actual edge weight. matrix[i][j] stores the weight of the edge from i to j, and a sentinel value — commonly 0, -1, ∞, or None depending on the context — is used to indicate the absence of an edge. For example, in a road network where edge weights represent distances in kilometres, the matrix might look like:

Here, a road of length 5 km connects A to B, a road of 3 km connects B to C, and a road of 2 km connects C back to A. The ∞ entries signal no direct road. Algorithms such as Floyd-Warshall, which finds shortest paths between all pairs of vertices, operate directly on this form of the adjacency matrix without any transformation.

Directed versus Undirected Graphs produce matrices with a critical structural difference. In a directed graph (digraph), an edge from vertex i to vertex j does not imply an edge from j to i. Therefore matrix[i][j] and matrix[j][i] can differ. The example above is directed: there is a road from C to A (weight 2) but no road from A to C (∞).

In an undirected graph, every edge is bidirectional. Adding edge (i, j) automatically implies edge (j, i). As a result, the matrix is always symmetric across its main diagonal: matrix[i][j] == matrix[j][i] for all i and j. Consider an undirected version of the four-vertex graph from earlier, where we add the reverse of every directed edge:

Notice that this matrix is a perfect mirror image of itself across the diagonal. This symmetry is not merely a nice property — it is an opportunity for optimisation. Because the upper triangle and the lower triangle contain identical information, only one of them strictly needs to be stored. Techniques such as a triangular matrix or a packed flat array can halve the memory requirement for undirected graphs, though this comes at the cost of slightly more complex index arithmetic.

Space Complexity is the most defining characteristic — and the most significant limitation — of the adjacency matrix. For a graph with V vertices, the matrix always allocates exactly V × V cells, regardless of how many edges actually exist. This gives a space complexity of O(V²).

When is this acceptable? For a dense graph, one in which the number of edges E is close to V², almost every cell in the matrix holds meaningful data. The memory overhead per edge is low because there are so many edges sharing the total allocation. The complete graph K₁₀ has 10 vertices and 45 undirected edges; its 10×10 matrix stores 100 cells but 45 of them carry real edge data — an efficiency of 45%. For K₁₀₀, the ratio climbs even higher.

For a sparse graph, however, the picture reverses dramatically. Consider a graph modelling the hyperlinks between web pages: billions of vertices, yet each page links to only tens or hundreds of others. The number of edges E is tiny relative to V². Storing a billion-by-billion matrix to represent a handful of edges per vertex is completely impractical. In such scenarios, the adjacency matrix wastes enormous memory holding zeroes that carry no information.

Time Complexity for Common Operations directly follows from the matrix structure:

• Edge existence check — O(1): To determine whether an edge exists between vertex i and vertex j, access matrix[i][j]. Array indexing in a two-dimensional structure is a constant-time operation. This is the single greatest strength of the adjacency matrix. No other standard graph representation achieves O(1) edge lookup without additional bookkeeping.
• Finding all neighbours of a vertex — O(V): To enumerate every vertex adjacent to vertex i, scan the entire row i and collect all positions j where matrix[i][j] ≠ 0. Even if vertex i has only two neighbours, you must examine all V entries in the row to be sure. This is O(V) regardless of the actual degree of the vertex.
• Adding or removing an edge — O(1): Inserting edge (i, j) means setting matrix[i][j] = 1 (or the edge weight). For an undirected graph, also set matrix[j][i] = 1. Either way, it is a constant number of assignment operations. Removing an edge is equally simple: set the relevant cell or cells back to 0.
• Adding a new vertex — O(V²): This is the most expensive structural change. A new vertex increases V to V+1, meaning the matrix must grow from V×V to (V+1)×(V+1). In most implementations this requires allocating a new, larger array and copying all existing data into it — an O(V²) operation. Frequently resizing a large adjacency matrix is therefore very costly.

A concrete implementation of an adjacency matrix in Python illustrates how straightforward the structure is to build and query:

class AdjacencyMatrix:
    def __init__(self, num_vertices):
        self.V = num_vertices
        # Initialise a V×V matrix filled with zeros
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, u, v, weight=1, directed=False):
        self.matrix[u][v] = weight
        if not directed:
            self.matrix[v][u] = weight   # Symmetry for undirected graphs

    def remove_edge(self, u, v, directed=False):
        self.matrix[u][v] = 0
        if not directed:
            self.matrix[v][u] = 0

    def has_edge(self, u, v):
        return self.matrix[u][v] != 0   # O(1) lookup

    def neighbours(self, u):
        # O(V) — must scan the entire row
        return [v for v in range(self.V) if self.matrix[u][v] != 0]

# Example usage
g = AdjacencyMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print(g.has_edge(0, 1))   # True
print(g.has_edge(0, 3))   # False
print(g.neighbours(0))    # [1, 2]

The has_edge method is a single list index operation — it cannot be faster. The neighbours method must iterate all V columns in the row; for a vertex with only two neighbours in a graph of 10,000 vertices, it still performs 10,000 comparisons.

Advantages of the Adjacency Matrix are most pronounced in specific, well-defined use cases:

• Constant-time edge queries make the adjacency matrix the right choice whenever an algorithm repeatedly asks "does edge (u, v) exist?" rather than "give me all neighbours of u." The Floyd-Warshall all-pairs shortest-path algorithm and certain matrix-based graph algorithms (including those using matrix exponentiation to count paths of length k) rely directly on this property.
• Simplicity of implementation is a meaningful practical advantage. Two-dimensional arrays are native to virtually every programming language. There are no linked lists, no hash maps, no auxiliary structures to manage. For teaching, prototyping, or small competitive programming problems, this simplicity is valuable.
• Dense graphs justify the memory cost. In graph colouring problems, clique detection, or dense network analysis where nearly all vertex pairs are connected, the adjacency matrix is not only efficient but natural. The proportion of wasted space approaches zero as the graph approaches completeness.
• Matrix operations apply directly. The adjacency matrix integrates naturally with linear algebra. Squaring the matrix A² gives, at entry (i, j), the number of distinct paths of length exactly 2 from vertex i to vertex j. More generally, Aᵏ[i][j] counts paths of length k. This connection between graph theory and matrix algebra enables efficient algorithms for reachability and counting problems.

Trade-offs and Limitations are equally important to understand, because choosing the wrong representation can make an otherwise correct algorithm impractically slow or memory-hungry:

• Quadratic memory growth is the dominant limitation. Doubling the number of vertices quadruples the memory consumption. A graph with 10,000 vertices requires a 10,000 × 10,000 matrix — 100 million cells. At 4 bytes per integer, that is 400 MB just for the matrix. For graphs with hundreds of thousands or millions of vertices, an adjacency matrix becomes completely infeasible.
• Traversal algorithms are penalised. Breadth-first search (BFS) and depth-first search (DFS) both need to enumerate the neighbours of a vertex at each step. With an adjacency matrix, this costs O(V) per vertex, making the full traversal O(V²). With an adjacency list, enumerating neighbours costs O(degree of vertex), and the full traversal costs O(V + E). For sparse graphs where E ≪ V², this difference is enormous — an algorithm that runs in seconds with an adjacency list may take hours with an adjacency matrix on the same graph.
• Dynamic graphs are expensive to manage. If the graph changes frequently — vertices are added or removed at runtime — the matrix must be resized. Each resize involves copying O(V²) data. Algorithms that construct graphs incrementally, such as certain online or streaming algorithms, should strongly prefer adjacency lists or other dynamic structures.
• Sparse graphs waste memory proportionally to their sparsity. If a graph has V vertices and only O(V) edges (common in trees, grids, and real-world networks), the adjacency matrix is V²/V = V times more memory-intensive than the data would justify. An adjacency list stores each edge exactly once (or twice for undirected graphs), giving O(V + E) space — a decisive advantage for sparse graphs.

The following table summarises the time and space complexities of the adjacency matrix alongside the adjacency list for direct comparison:

The choice between an adjacency matrix and alternative representations ultimately comes down to the characteristics of the specific graph and the operations that will be performed most frequently. When the graph is dense, static, and edge-existence queries dominate, the adjacency matrix is excellent. When the graph is sparse, dynamic, or traversal-heavy, the adjacency list's O(V + E) space and neighbour-enumeration costs make it the better tool. A practitioner who thoroughly understands both representations — and the trade-offs summarised above — can make that choice confidently and justify it rigorously.