Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 36 · Graphs and Representations

The Adjacency Matrix

Represent a graph as an adjacency matrix: build it in Python and NumPy, read degrees from rows, handle directed and weighted graphs, and count walks with matrix powers.

A drawing is great for people but useless for a program. To compute with a graph we need a data structure. The first and most mathematical one is the adjacency matrix: a square table with one row and one column per vertex, where the entry in row i, column j says whether i and j are connected.

Number the vertices 0, 1, ..., n-1. The adjacency matrix A is an n × n matrix with A[i][j] = 1 if there is an edge from i to j, and 0 otherwise.

graph LR
  0 --- 1
  0 --- 2
  1 --- 2
  2 --- 3

For this graph the matrix is:

TEXT
      0  1  2  3
  0 [ 0  1  1  0 ]
  1 [ 1  0  1  0 ]
  2 [ 1  1  0  1 ]
  3 [ 0  0  1  0 ]

Properties

  • For an undirected graph the matrix is symmetric: A[i][j] = A[j][i], because an edge works in both directions.
  • For a simple graph the diagonal is all zeros (no loops).
  • The sum of row i is the degree of vertex i. The sum of all entries is 2m, the handshake lemma again.
  • For a directed graph the matrix is usually not symmetric: row sums are out-degrees and column sums are in-degrees.
  • For a weighted graph store the weight in the cell instead of 1, and use 0 (or inf) for "no edge", choosing carefully if a weight of 0 is meaningful.
Python Build a matrix with NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cost of the matrix

The matrix always uses n² cells, no matter how few edges exist.

Operation Adjacency matrix
Memory O(n²)
Is u adjacent to v? O(1)
List neighbors of v O(n) (scan the row)
Add or remove an edge O(1)
Visit all edges O(n²)

That makes the matrix excellent for dense graphs and for algebra, but wasteful for a sparse graph with a million vertices (a million squared cells is far too many). The adjacency list fixes that.

Directed and weighted versions

Python Directed and weighted matrices

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using inf for "no edge" and 0 on the diagonal is the convention that the Floyd-Warshall style algorithms expect.

Counting walks with matrix powers

Here is the magic of the matrix: A² counts walks of length 2. The entry (A²)[i][j] is sum over k of A[i][k]·A[k][j], which counts the middle vertices k that are adjacent to both i and j. In general:

(A^k)[i][j] is the number of walks of length exactly k from i to j.

On the diagonal, (A²)[i][i] equals deg(i), and trace(A³) = 6 × (number of triangles) because each triangle is counted six times (3 starting points × 2 directions).

Python Counting walks and triangles

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Walk counting is the seed of spectral graph theory, where eigenvalues of A reveal deep structure.

When to choose the matrix

Pick the adjacency matrix when the graph is small or dense, when you need fast "is there an edge?" tests, or when you plan to use linear algebra (powers, eigenvalues, scipy routines). Pick a list when the graph is large and sparse.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In the adjacency matrix of a simple undirected graph, the sum of row i equals:

    Each 1 in row i marks a neighbor of i, so the row sum is deg(i).
  2. 2. How much memory does an adjacency matrix of n vertices need?

    It has n rows and n columns regardless of how many edges exist.
  3. 3. What does the entry (A^3)[i][j] count?

    Powers of the adjacency matrix count walks: the exponent is the walk length.
  4. 4. For an undirected graph the adjacency matrix is:

    An edge {i, j} sets both A[i][j] and A[j][i], so the matrix equals its transpose.

Summary

  • The adjacency matrix A has A[i][j] = 1 when i and j are joined.
  • Undirected graphs give symmetric matrices; row sums are degrees.
  • Directed graphs use one cell per arc; weighted graphs store weights.
  • Space is O(n²); an edge test is O(1).
  • A^k[i][j] counts walks of length k, and trace(A³)/6 counts triangles.

Next: The Adjacency List