Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Adjacency Matrix

For a graph with vertices, the adjacency matrix is an matrix with if there is an edge between and , and otherwise.

Properties:

  • diagonal entries are if no vertex has a self-loop
  • the matrix of an undirected graph is symmetric,
  • it always has entries, so the space complexity is

For a directed graph, means an edge from to . At least one pair has but , so the matrix is not symmetric, e.g. is an edge but is not.

Adjacency Lists

An adjacency list keeps, for each vertex, a list of its neighbours (for a digraph, only the vertices it has an out-edge to). In Python this is a dictionary:

graph = {
    1: [2, 5],
    2: [1, 3, 4],
    3: [2, 5],
    4: [2],
    5: [1, 3],
}

In an undirected graph each edge appears twice: in 's list and in 's list. With vertices and edges there are list heads and list nodes, so the space complexity is .

Weighted Graphs

A cost adjacency matrix stores = cost of edge , e.g. the cost from to is .

As a Python dictionary, each vertex maps to another dictionary of neighbour and weight. For an undirected graph both directions must be listed:

graph = {
    1: {2: 58, 5: 55},
    2: {1: 58, 3: 20, 4: 89},
    3: {2: 20, 5: 23},
    4: {2: 89},
    5: {1: 55, 3: 23},
}

Matrix or Lists

Adjacency matrixAdjacency lists
Space
Dense graph ()about equally efficientabout equally efficient
Sparse graph ()many wasted zerosmore efficient
Check one edgescan a list

Adjacency lists are usually the better computational choice, while matrices can be more intuitive. A representation is only a storage format: an undirected graph has the same adjacency lists as a certain directed graph, so the lists alone do not tell you whether the graph is directed. Converting lists into a matrix is a common exam task:

def adjlist_to_matrix(adj, n):        # vertices 1..n
    A = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in adj[i]:
            A[i][j] = 1
    return A

The costs of graph operations in each format are listed in Big-O Summary Tables.