Beginning Java Data Structures and Algorithms

Adjacency Matrix Representation

The adjacency list representation of a graph provides a compact way to represent sparse graphs, for example, those for which |E| is much less than |V|². Even though it is a representation that is useful for a lot of algorithms (which we will visit later), it does not support some features. For example, one cannot quickly tell whether there is an edge connecting two given vertices. In order to determine if u and v are connected, one has to go through the adjacency list of u to find an edge connecting it to v. Since the adjacency list of u can have at most E edges, this procedure runs in O(E) time. One alternative representation that remedies this disadvantage at the cost of using asymptotically more memory is ...