An adjacency matrix is a way of representing an
, whose entries are boolean
The matrix entry is defined as
In this representation, the operations
involve setting or reading the matrix entry
These operations clearly take constant time per operation.
Where the adjacency matrix performs poorly is with the and operations. To implement these, we must scan all entries in the corresponding row or column of and gather up all the indices, , where , respectively , is true. These operations clearly take time per operation.
Another drawback of the adjacency matrix representation is that it is large. It stores an boolean matrix, so it requires at least bits of memory. The implementation here uses a matrix of values so it actually uses on the order of bytes of memory. A more careful implementation, which packs boolean values into each word of memory, could reduce this space usage to words of memory.
Despite its high memory requirements and poor performance of the and operations, an AdjacencyMatrix can still be useful for some applications. In particular, when the graph is dense, i.e., it has close to edges, then a memory usage of may be acceptable.
The AdjacencyMatrix data structure is also commonly used because algebraic operations on the matrix can be used to efficiently compute properties of the graph . This is a topic for a course on algorithms, but we point out one such property here: If we treat the entries of as integers (1 for and 0 for ) and multiply by itself using matrix multiplication then we get the matrix . Recall, from the definition of matrix multiplication, that