Adjacency Matrix

From Algorithmist
Jump to navigation Jump to search

We can represent an n-node graph by an n-by-n matrix. Assume the nodes are labeled . Then the adjacency matrix is an n by n matrix whose entry is defined to be

  • 1, if there is an edge from to
  • 0, otherwise.

Note that an undirected graph corresponds to a symmetric matrix.

We could instead put weights on the edges, and define to be

  • 0, if there is no edge from to
  • , if there is an edge, and is its weight.

See Graph Data Structures for another definition of the adjacency matrix.

Multiplication of the Adjacency Matrix[edit]

Note that the entry of an unweighted adjacency matrix simply counts the number of paths from to 'of length one'. A useful fact is that similarly, the entry of the th power of the adjacency matrix counts the number of paths of length exactly from to . By using repeated squaring we can sometimes count paths quickly.