Notes

Adjacency Matrix

2 min read

Adjacency matrix is a graph representation that uses a table to show whether pairs of nodes are connected.

For a graph with n nodes, the matrix is usually n x n. Each cell represents whether an edge exists between two nodes.

For example:

    A B C
A   0 1 1
B   1 0 0
C   1 0 0

This represents a graph where A is connected to B and C.

Adjacency matrices are useful when:

  • The graph is dense
  • Fast edge lookup is important
  • The number of nodes is known and not too large

Common operations:

  • Checking whether an edge exists: O(1)
  • Finding all neighbors of a node: O(V)
  • Space usage: O(V^2)

The main tradeoff is space. An adjacency matrix can waste memory when the graph has few edges.

flowchart TD
    Matrix["matrix"] --> RowA["A: 0 1 1"]
    Matrix --> RowB["B: 1 0 0"]
    Matrix --> RowC["C: 1 0 0"]

Anki

id: adjacency-matrix-definition deck: Computer Science::Data Structures tags: data-structures graph adjacency-matrix

Q: In an adjacency matrix, how do you check whether node A connects to node B? A: Look at the cell for row A and column B.

id: adjacency-matrix-edge-lookup deck: Computer Science::Data Structures tags: data-structures graph adjacency-matrix

Q: What is the main downside of an adjacency matrix for a graph with very few edges? A: It still stores a full node-by-node table, so it can waste a lot of space.

Graph View