The Adjacency Matrix
Chapter Ninety
Syllabus topic Module 2, "Graph: Graph Representation using adjacency matrix and adjacency list"
Pages 285 to 287 of 411
In one line
An adjacency matrix is an n by n table where the cell at row i, column j says whether there is an edge from vertex i to vertex j, which makes that question instant and costs n squared memory whatever the graph.
The representation
Number the vertices 0 to n-1. Make an n by n table. Then:
matrix[i][j] = 1 if there is an edge from i to j, else 0
For a weighted graph the cell holds the weight instead of 1, and a special value such as infinity means no edge. Zero cannot mean "no edge" in a weighted graph, because zero is a legitimate weight.
For an undirected graph the matrix is symmetric: matrix[i][j] equals matrix[j][i], because an edge joins both ways. That symmetry is a useful check and it also means half the table is redundant.
Built and printed
class MatrixGraph:
"""A graph as an n by n table of 0s and 1s."""
def __init__(self, labels, directed=False):
self.labels = list(labels)
self.index = {name: i for i, name in enumerate(self.labels)}
n = len(self.labels)
self.matrix = [[0] * n for _ in range(n)]
self.directed = directed
def add_edge(self, u, v):
i, j = self.index[u], self.index[v]
self.matrix[i][j] = 1
if not self.directed:
self.matrix[j][i] = 1
def has_edge(self, u, v):
return self.matrix[self.index[u]][self.index[v]] == 1
def neighbours(self, v):
i = self.index[v]
return [self.labels[j] for j in range(len(self.labels))
if self.matrix[i][j] == 1]
def degree(self, v):
return sum(self.matrix[self.index[v]])
def is_symmetric(self):
n = len(self.labels)
return all(self.matrix[i][j] == self.matrix[j][i]
for i in range(n) for j in range(n))
def show(self):
header = " " + " ".join("%3s" % name for name in self.labels)
rows = [header]
for name, row in zip(self.labels, self.matrix):
rows.append("%4s " % name + " ".join("%3d" % cell for cell in row))
return "\n".join(rows)
g = MatrixGraph(["A", "B", "C", "D", "E"])
for a, b in (("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D")):
g.add_edge(a, b)
print("the adjacency matrix:")
print(g.show())
print()
print("has_edge(A, B) :", g.has_edge("A", "B"), " one cell, O(1)")
print("has_edge(A, D) :", g.has_edge("A", "D"))
print("neighbours of B :", g.neighbours("B"), " a whole row, O(n)")
print("degree of B :", g.degree("B"))
print("symmetric :", g.is_symmetric(), " (undirected graphs always are)")
print("E has no edges :", g.neighbours("E") == [])
print()
print("cells in the table:", len(g.labels) ** 2)
print("edges in the graph:", sum(sum(row) for row in g.matrix) // 2)
print("so %d cells hold a 1 and %d hold a 0"
% (sum(sum(row) for row in g.matrix),
len(g.labels) ** 2 - sum(sum(row) for row in g.matrix)))the adjacency matrix:
A B C D E
A 0 1 1 0 0
B 1 0 1 1 0
C 1 1 0 1 0
D 0 1 1 0 0
E 0 0 0 0 0
has_edge(A, B) : True one cell, O(1)
has_edge(A, D) : False
neighbours of B : ['A', 'C', 'D'] a whole row, O(n)
degree of B : 3
symmetric : True (undirected graphs always are)
E has no edges : True
cells in the table: 25
edges in the graph: 5
so 10 cells hold a 1 and 15 hold a 0The Adjacency Matrix
Twenty-five cells for five vertices and five edges. Ten cells hold a 1 (each edge appearing twice) and fifteen hold a 0, including the whole of row E and column E.
What it is good at
has_edge is O(1). One cell is read. No other representation does this, and it is the matrix's whole argument.
Adding or removing an edge is O(1). One cell is written.
The structure is simple, which matters more than it sounds: a two dimensional array needs no allocation, no pointers and no care, and in C it is a single block.
Weights fit naturally. The cell holds the weight. Many graph algorithms expressed as matrix operations, which is a real technique, rely on this.
What it is bad at
Memory is n squared whatever the graph. A graph of 10,000 vertices needs 100 million cells even if there are only 20 edges. That is the decisive weakness.
neighbours(v) is O(n). The whole row must be scanned, including every zero. Since every traversal and search is a loop over neighbours (chapter 89), this makes every graph algorithm O(n squared) on a matrix, even when the graph has very few edges.
Adding a vertex is O(n squared), because the table must be rebuilt one row and one column larger.
print("%10s %14s %14s %16s %s"
% ("vertices", "matrix cells", "sparse edges", "cells per edge", "useful"))
for n in (10, 100, 1000, 10000):
cells = n * n
edges = 2 * n # a sparse graph: average degree 4
print("%10d %14d %14d %16.0f %13.4f%%"
% (n, cells, edges, cells / edges, 100 * 2 * edges / cells))
print()
print("at 10,000 vertices with 20,000 edges, 99.96% of the matrix is zero.") vertices matrix cells sparse edges cells per edge useful
10 100 20 5 40.0000%
100 10000 200 50 4.0000%
1000 1000000 2000 500 0.4000%
10000 100000000 20000 5000 0.0400%
at 10,000 vertices with 20,000 edges, 99.96% of the matrix is zero.At 10,000 vertices with an average of 4 edges each, the matrix is 99.96 per cent zeros. That is 100 million cells to store 20,000 facts.
When to use it
Despite that, the matrix is the right choice in three cases, and an answer should name them:
When the graph is dense, close to n(n-1)/2 edges. Then most cells are used and the O(1) has_edge comes free.
The Adjacency Matrix
When has_edge is the dominant operation. If the program mostly asks "are these two joined" rather than "who are this one's neighbours", the matrix wins outright.
When n is small. For twenty vertices the matrix is 400 cells, which is nothing, and the simplicity is worth more than the memory.
Quick revision
- An n by n table; cell [i][j] is 1 when there is an edge from i to j, or the weight in a weighted graph.
- In a weighted graph, "no edge" must be infinity or a sentinel, never 0, since 0 is a valid weight.
- An undirected graph's matrix is symmetric, so half of it is redundant.
- has_edge and edge insertion and removal are O(1).
- neighbours(v) is O(n), which makes every graph algorithm O(n squared) on a matrix.
- Memory is n squared whatever the graph: at 10,000 vertices and 20,000 edges it is 99.96 per cent zeros.
- Adding a vertex is O(n squared), since the table is rebuilt.
- Use it for dense graphs, when has_edge dominates, or when n is small.
Test yourself
1. What does cell [i][j] hold, in an unweighted and in a weighted graph? In an unweighted graph, 1 if there is an edge from i to j and 0 otherwise. In a weighted graph, the weight, with infinity or a sentinel for no edge.
2. Why can 0 not mean "no edge" in a weighted graph? Because 0 is a legitimate weight, so the two cases would be indistinguishable.
3. Which operations are O(1), and which is O(n)? has_edge, add_edge and remove_edge are O(1). neighbours(v) is O(n), because the whole row must be scanned.
4. Why does an O(n) neighbours make every graph algorithm O(n squared)? Because every traversal, search and shortest path is a loop over neighbours for each vertex, so n vertices times O(n) per vertex is O(n squared), however few edges there are.
5. Give the measured waste at 10,000 vertices with 20,000 edges. The matrix has 100,000,000 cells of which 99.96 per cent are zero.
6. Name three situations where the matrix is the right choice. When the graph is dense; when has_edge is the dominant operation; and when the number of vertices is small enough that n squared is trivial.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.