Course contentsShow
← Computer Science
Lesson 669 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Adjacency Matrix: Structure and Memory

Learn how to represent graphs using a 2D array where entry (i,j) indicates an edge between vertices i and j.

Adjacency Matrix: Structure and Memory

What You'll Learn

You'll learn how to represent graphs using a 2D array where each entry tells you whether an edge exists between two vertices.

The Core Idea

An adjacency matrix is one of the most straightforward ways to store a graph in memory. Imagine you have a graph with n vertices numbered 0 through n-1. You create a 2D array (a matrix) of size n × n. Each cell at position (i, j) answers the question: "Is there an edge from vertex i to vertex j?"

For an unweighted graph, the matrix stores Boolean-like values:

  • matrix[i][j] = 1 (or true) means an edge exists from vertex i to vertex j
  • matrix[i][j] = 0 (or false) means no edge exists

For a weighted graph, instead of just 1 or 0, you store the edge weight at matrix[i][j], and use a special value (like infinity or -1) to indicate "no edge."

Undirected vs Directed

In an undirected graph, if there's an edge between vertices i and j, both matrix[i][j] and matrix[j][i] are set (the matrix is symmetric). In a directed graph, only the appropriate direction is marked.

Memory Footprint

The adjacency matrix always uses O(n²) space, regardless of how many edges actually exist. This makes it memory-intensive for sparse graphs (graphs with few edges) but efficient for dense graphs where most vertex pairs are connected.

Key Takeaway: An adjacency matrix uses a 2D array of size n×n to represent a graph, where each cell indicates edge presence or weight, consuming O(n²) memory regardless of edge count.