Let G(V,E) be a graph with |V|=n vertices. Its adjacency matrix
is an n×n array whose (i,j)th entry is
aij={1if there is an edge from vi to vj0otherwise.
For undirected graphs, the matrix is symmetric since an edge {u,v} can be taken in either
direction.
The biggest convenience of this format is that the presence of a particular edge can be
checked in constant time, with just one memory access. On the other hand the matrix takes
up O(n2) space, which is wasteful if the graph does not have very many edges.