liveBook · Manning

Adjacency matrix

As explained in Algorithms Every Programmer Should Know

An adjacency matrix is a two-dimensional array whose entries indicate whether pairs of graph vertices are connected.

An adjacency matrix represents a graph with a two-dimensional array: rows and columns correspond to vertices, and each entry records whether a pair is connected. section 1.4.5

Read the entries this way:

  • A 1 marks a connection between the row and column vertices; a 0 marks no connection. section 1.4.5
  • Unlike an adjacency list, which stores only each vertex’s neighbors, the matrix lays out connections in a two-dimensional array. section 1.4.5
Figure 1.12 The two primary data structures for graph traversals. Left: Simple graph representation with four nodes connected to each other. Middle: An adjacency matrix maps connections from one node to another, denoting them by the value 1 in the matrix and otherwise 0. Right: An adjacency list showing a key-value dictionary connecting to neighboring nodes only.

Compare the graph, its matrix, and its adjacency list to see how each represents the same connections. section 1.4.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines rows, columns, and 1/0 entries, but provides no matrix implementation or complexity analysis.
Examples
Uses a four-node graph diagram to show connections as 1s and absent connections as 0s.
What you can do after
Understand how a matrix records graph connections and compare it with an adjacency list.
How it connects
Connects graph representation to vertices, edges, adjacency lists, and directed or undirected graphs.

Also explained in

Compare how 9 books explain adjacency matrix →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.