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
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.