Processing math: 100%

Glossary

Algo: Adjacency matrix

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.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.