Which Representation: The Costs, Measured

memory, in units stored (matrix cells against list entries):
vertices      edges   matrix cells   list entries    list uses
      10         15            100             30        30.0%
     100        194          10000            388         3.9%
    1000       1992        1000000           3984         0.4%

Workload one: a full traversal

Every traversal, search and shortest path in the chapters that follow does the same thing: it asks each vertex for its neighbours. So that is the workload to measure.

class CountingMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0] * n for _ in range(n)]
        self.probes = 0

    def add_edge(self, i, j):
        self.matrix[i][j] = 1
        self.matrix[j][i] = 1

    def neighbours(self, i):
        found = []
        for j in range(self.n):
            self.probes += 1
            if self.matrix[i][j]:
                found.append(j)
        return found


class CountingList:
    def __init__(self, n):
        self.n = n
        self.adjacent = [[] for _ in range(n)]
        self.probes = 0

    def add_edge(self, i, j):
        self.adjacent[i].append(j)
        self.adjacent[j].append(i)

    def neighbours(self, i):
        found = []
        for k in self.adjacent[i]:
            self.probes += 1
            found.append(k)
        return found


def sparse_edges(n):
    pairs = set()
    for i in range(n):
        for j in ((i + 1) % n, (i * 7 + 3) % n):
            if i != j:
                pairs.add((min(i, j), max(i, j)))
    return sorted(pairs)


def visit_everyone(g):
    for v in range(g.n):
        g.neighbours(v)
    return g.probes


print("one full pass over a sparse graph, asking every vertex for its neighbours:")
print("%8s %8s %14s %14s %16s"
      % ("vertices", "edges", "matrix probes", "list probes", "matrix does more"))
for n in (10, 100, 1000, 2000):
    edges = sparse_edges(n)
    m = CountingMatrix(n)
    l = CountingList(n)
    for i, j in edges:
        m.add_edge(i, j)
        l.add_edge(i, j)
    mp = visit_everyone(m)
    lp = visit_everyone(l)
    print("%8d %8d %14d %14d %15.0fx"
          % (n, len(edges), mp, lp, mp / lp))

print()
print("the matrix reads n squared cells to find 2E edges, whatever E is.")
print("the list reads 2E entries and nothing else.")

one full pass over a sparse graph, asking every vertex for its neighbours:
vertices    edges  matrix probes    list probes matrix does more
      10       15            100             30               3x
     100      194          10000            388              26x
    1000     1992        1000000           3984             251x
    2000     3996        4000000           7992             501x

the matrix reads n squared cells to find 2E edges, whatever E is.
the list reads 2E entries and nothing else.

The matrix count is exactly n squared every time, 100 and 10,000 and 1,000,000 and 4,000,000, because the row scan does not care how many of the cells are edges. The list count is exactly the number of entries, which is twice the edges: 30 for 15 edges, 7,992 for 3,996. The gap on a sparse graph grows with n without limit, from 3 times at ten vertices to 501 times at two thousand.

This single table is why every algorithm in the following chapters is written against an adjacency list. A traversal that is O(V + E) on a list becomes O(V squared) on a matrix.

Workload two: asking "are these two joined"

Now the question the matrix was built for.

class CountingMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0] * n for _ in range(n)]
        self.probes = 0

    def add_edge(self, i, j):
        self.matrix[i][j] = 1
        self.matrix[j][i] = 1

    def has_edge(self, i, j):
        self.probes += 1
        return self.matrix[i][j] == 1


class CountingList:
    def __init__(self, n):
        self.n = n
        self.adjacent = [[] for _ in range(n)]
        self.probes = 0

    def add_edge(self, i, j):
        self.adjacent[i].append(j)
        self.adjacent[j].append(i)

    def has_edge(self, i, j):
        for k in self.adjacent[i]:
            self.probes += 1
            if k == j:
                return True
        return False


def sparse_edges(n):
    pairs = set()
    for i in range(n):
        for j in ((i + 1) % n, (i * 7 + 3) % n):
            if i != j:
                pairs.add((min(i, j), max(i, j)))
    return sorted(pairs)


def dense_edges(n):
    return [(i, j) for i in range(n) for j in range(i + 1, n)]


def quiz(g, n):
    """n deterministic queries, some hits and some misses."""
    answers = 0
    for i in range(n):
        if g.has_edge(i, (i * 13 + 5) % n):
            answers += 1
    return g.probes, answers


print("%8s %8s %10s %14s %14s"
      % ("graph", "vertices", "queries", "matrix probes", "list probes"))
for n in (100, 500):
    for name, edges in (("sparse", sparse_edges(n)), ("dense", dense_edges(n))):
        m, l = CountingMatrix(n), CountingList(n)
        for i, j in edges:
            m.add_edge(i, j)
            l.add_edge(i, j)
        mp, _ = quiz(m, n)
        lp, _ = quiz(l, n)
        print("%8s %8d %10d %14d %14d" % (name, n, n, mp, lp))

print()
print("the matrix does exactly one probe per query in all four rows above.")
print("on the dense graph of 500 vertices every list holds 499 entries,")
print("so the list does hundreds of times the work for the same answer.")

   graph vertices    queries  matrix probes    list probes
  sparse      100        100            100            384
   dense      100        100            100           4999
  sparse      500        500            500           1985
   dense      500        500            500         124999

the matrix does exactly one probe per query in all four rows above.
on the dense graph of 500 vertices every list holds 499 entries,
so the list does hundreds of times the work for the same answer.

The matrix does exactly one probe per query whatever the graph: 100, 100, 500, 500. On the sparse graphs the list pays a few probes per query, 384 and 1,985, because the lists are short. On the dense graph of 500 vertices the list pays 124,999, which is 250 times the matrix's 500, because every list holds 499 entries and a miss must read all of them.

So the honest summary is not "lists are better". It is: lists are better for traversal and for memory, matrices are better for edge lookup, and density decides how much that matters.

The table to reproduce in an answer

Advantages and disadvantages, stated plainly

The matrix's advantages. Instant edge lookup; instant edge insertion and removal; a simple fixed structure with no pointers; weights sit naturally in the cells; symmetry gives a free correctness check on undirected graphs.

The matrix's disadvantages. O(V squared) memory even for an empty graph; a neighbour scan that reads every zero; O(V squared) to add a vertex; and consequently O(V squared) for every traversal.

The list's advantages. Memory proportional to the edges that exist; a neighbour scan that touches only real edges, so traversals are O(V + E); O(1) to add a vertex; and per-edge data such as weights fits in the entry.

The list's disadvantages. Edge lookup and edge removal are O(degree), not O(1); on a dense graph that degree is close to V; and each entry costs a reference, possibly with a next pointer, where a matrix cell could be a single bit.

What to say when asked to choose

Say the rule, then the reason:

Use an adjacency list unless the graph is dense or the program's main question is whether two given

vertices are joined. Real graphs, such as road networks, web links and social graphs, are sparse, so

the list is the default; and since BFS, DFS and Dijkstra all work by asking for neighbours, the list

keeps them at O(V + E) where the matrix would force O(V squared).

Quick revision

• Probes are counted, not seconds: one cell read on a matrix, one entry read on a list.
• A full traversal costs exactly V squared probes on a matrix and exactly 2E on a list.
• So a traversal is O(V + E) on a list and O(V squared) on a matrix: the reason every algorithm here uses a list.
• has_edge is one probe on a matrix always, and O(degree) on a list.
• On a dense graph the list's has_edge collapses, because its lists hold nearly every vertex.
• Memory: V squared cells always, against V + 2E entries.
• Matrix advantages: O(1) lookup and edge updates, simple structure, natural weights, symmetry check.
• List advantages: edge-proportional memory, O(1) vertex insertion, O(V + E) traversal.
• Default to the list; choose the matrix for dense graphs, small V, or lookup-dominated work.

Test yourself

1. Why does this chapter count probes rather than seconds? Because a probe is a fixed unit of work that is identical on every machine and interpreter, while a timing varies with hardware, interpreter and load, so it cannot be quoted as a fact.

2. How many probes does a full traversal cost on each representation? Exactly V squared on a matrix, because every row is scanned in full, and exactly 2E on a list, because only real edges are read.

3. Give the complexity of BFS on each representation and explain the difference. O(V + E) on a list and O(V squared) on a matrix. BFS asks each vertex for its neighbours; the list answers in O(degree) and the matrix in O(V).

4. State one operation where the matrix is strictly better and one where the list is. has_edge is O(1) on a matrix and O(degree) on a list. Adding a vertex is O(1) on a list and O(V squared) on a matrix.

5. When does the list's has_edge become a serious weakness? On a dense graph, where a vertex's list holds nearly every other vertex, so a search of it approaches O(V).

6. Can a matrix ever use less memory than a list? Yes. For a very dense graph, where a cell can be a single bit while each list entry carries a vertex reference and possibly a next pointer.

7. Give the one-sentence rule for choosing. Use an adjacency list unless the graph is dense or the dominant question is whether two given vertices are joined.