Adjacency Matrix

In the last post, we explored how a graph can be represented using an adjacency list. We’ll now look at how an adjacency matrix can also be used.

Disclaimer

This post is mainly for me to jot down points about Adjacency Matrices. If this is helpful to you in some way, please don’t hesitate to reach out. I would appreciate the feedback!

What is an Adjacency Matrix?

An adjacency matrix is a square matrix representation of a finite graph. The elements indicate whether a pair of vertices is adjacent to each other.

A graph with V vertices can be represented with a V x V matrix (V rows and V columns) where:

Therefore, a point (i, j) represents an edge starting from i and ending at j.

If the value at this point (i, j) is:

Building an Adjacency Matrix

We have previously looked at the following graph:

In order to build this matrix, we would first need to create a VxV matrix full of zeros. V is the number of vertices which for this graph is 6 so we need to build a matrix consisting of 6 rows and 6 columns.

The 6x6 matrix looks like this:

The rows and columns are enumerated from 0 until 5 which corresponds with vertices A to F respectively.

We now go through each vertex and mark each node is connected to with a 1. Let’s start with vertex A.

Vertex A

Vertex A is connected to both B and C.

  1. Find the row corresponding to A: 0
  2. Then we find the column for B: 1
  3. Mark this point at row 0 and column 1 ((0, 1)) with a value of 1
  4. Then we find the column for C: 2
  5. Mark this point row 0 and column 2 ((0, 1)) with a value of 1

The resulting row for A now looks like:

Vertex B

Vertex B is connected to both D and E.

  1. Find the row corresponding to B: 1
  2. Then we find the column for D: 3
  3. Mark this point at row 1 and column 3 ((1, 3)) with a value of 1
  4. Then we find the column for E: 4
  5. Mark this point row 1 and column 4 ((1, 4)) with a value of 1

The resulting row for B now looks like:

Vertex C

Vertex C is only connected to F.

  1. Find the row corresponding to C: 2
  2. Then we find the column for F: 5
  3. Mark this point at row 2 and column 5 ((2, 5)) with a value of 1

The resulting row for C now looks like:

Vertex D, E, and F

Vertex D, E, and F have no adjacent nodes.

Therefore, their respective rows can remain as zeros.

The Result

The completed adjacency matrix for the graph looks like:

Recall:

Implementation

The adjacent matrix can be implemented using a 2D array (aka an array of arrays).

The above matrix would be defined in Swift as follows:

let matrix: [[Int]] = [
    [0, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

Checking for Existence

If we wanted to determine whether there exists an edge between two vertices, we can do a lookup in this array to determine this. Recall that a value of 1 signifies the existence of an edge.

func hasEdge(in matrix: [[Int]], from row: Int, to col: Int) -> Bool {
    // 1
    guard isIndexValid((row, col), in: matrix) else { return false }
    // 2
    return matrix[row][col] == 1
}
  1. Calls a helper function that takes in a tuple of the row and column pair and returns if it’s valid for the given matrix
  2. Accesses the value at the given row and column and verifies if it equals to 1
    • This is sometimes easier to follow when separated:
        let rows = matrix[row]
        return rows[col] == 1
      

Depth First Search (DFS)

When we did DFS on the graph, we did pre-order traversal that follows these steps:

  1. Visit node
  2. Visit left child
  3. Visit right child

The result of the traversal was a visitation order as follows:

A -> B -> D -> E -> C -> F

The DFS traversal for a matrix requires that we traverse as follows:

// This algorithm is courtesy of my colleague Michelle Lee!
func dfsMatrix(_ matrix: [[Int]], row: Int = 0) {
    guard !matrix.isEmpty else { return }

    print(edgesLookup[row])
    // 1
    rowsVisited.insert(row)

    // 2
    let colCount = matrix[row].count
    for col in 0..<colCount {
        // 3
        if matrix[row][col] == 1 && !rowsVisited.contains(col) {
            // 4
            dfsMatrix(matrix, row: col)
        }
    }
}
  1. After printing the node that corresponds to the row, add this row to our set of visited nodes
  2. Grab the count of columns for this given row and create a loop from 0 up to colCount
  3. Check if the value at (row, col) is equal to 1 and that we haven’t visited this node before
  4. Using this column col, repeat the DFS starting at this row.

The output should be the same as before:

A -> B -> D -> E -> C -> F

This does assume that the first row has at least one edge through which for most cases is a valid assumption.

Summary

An adjacency matrix is another way to represent a graph that makes lookups very quick.

However, there is often a lot of space required to define the graph. For large graphs, this can become quite inefficient.

A common example where you’ll see adjacency matrices is in this classic interview question: Island Problem. The example code can be found here.

Tradeoffs

Pros:

Cons:

Additional Resouces