Course contentsShow
← Machine Learning and Deep Learning
Lesson 2484 of 3,53854. Graph Neural NetworksFree lesson

Graph Representations: Adjacency Matrix

Represent graphs as adjacency matrices; understand sparsity, symmetry for undirected graphs, and memory complexity.

Graph Representations: Adjacency Matrix

What you'll learn: How to represent graph structures using adjacency matrices and understand their key properties.

The Core Idea

Once you've defined a graph with nodes and edges, you need a way to store it in memory that computers can work with. The adjacency matrix is one fundamental representation: a square matrix where rows and columns represent nodes, and cell values indicate whether an edge exists between them.

For a graph with n nodes, you create an n × n matrix A. If there's an edge from node i to node j, then A[i][j] = 1; otherwise, A[i][j] = 0.

Key Properties

Sparsity

Real-world graphs (social networks, molecules) are typically sparse—most nodes connect to only a few others, not everyone. This means the adjacency matrix is mostly zeros, which wastes memory. A matrix storing a million-node graph with average degree 10 would be 99.999% zeros!

Symmetry for Undirected Graphs

In undirected graphs (friendships, molecular bonds), if node i connects to node j, then j also connects to i. The adjacency matrix becomes symmetric: A[i][j] = A[j][i]. You only need to store half of it, though in practice we often keep both for simplicity.

Memory Complexity

The adjacency matrix requires O(n²) memory regardless of how many edges exist. For 10,000 nodes, that's 100 million entries—even if you only have 50,000 edges. This makes adjacency matrices impractical for large sparse graphs, but they shine for dense graphs or when you need fast edge lookups.

Analogy

Think of a conference attendance sheet where rows and columns are people's names. A checkmark at row Alice, column Bob means "Alice knows Bob." Most cells are blank (sparse), and if it's a friendship table, it's symmetric (Alice knows Bob = Bob knows Alice).

Key Takeaway: Adjacency matrices offer O(1) edge lookup but waste memory on sparse graphs with O(n²) storage, and are symmetric for undirected graphs.