Graph Theory • Representations

Adjacency Matrix

An Adjacency Matrix is a square matrix used to represent a finite graph. The element at row i and column j indicates if an edge exists between vertex i and j.

Try Interactive Simulator

Overview

A 2D array representation where nodes are indices. A '1' at (i, j) means an edge exists; a '0' means no connection.

Symmetry

For undirected graphs, the matrix is symmetric across the main diagonal (M[i,j] == M[j,i]).

Fast Lookups

Checking if Node A connects to Node B takes constant time O(1), making it ideal for dense graphs.

Space Tradeoff

It always takes V² space, even if the graph has very few edges. This makes it inefficient for sparse graphs.