Redirected from Adjacency matrices
- for a graph with n vertices and m edges, we store an n by n matrix
- a 1 or similar value at position i, j in the matrix is used to indicate the presence of an edge between vertices i and j
- alternatively, for a weighted graph, we can use the edge weight as the value
- directed graphs can use the sign of the value (positive or negative) to indicate the direction of the edge
- for maximal density, we can use as little as a single bit to encode each value (in the case of an undirected, unweighted graph)
The matrix itself can be stored in any convenient way; it could be a bit string, or a multidimensional array. If the matrix is relatively sparse, we can look at using a special-purpose data structure to represent the sparse matrix.