2.3 Representing Sparse Graphs as Adjaceny Lists
An adjacency list is a data structure for representing adjacency relationships in sparse graphs. The adjacency list of is actually a set of linked lists. Each vertex is the head of a list. Vertices adjacent to form the body of each list. If a vertex is not adjacent to any other vertices its list is empty.
The storage required to implement an adjacency list is proportional to . When is represented as an adjacency list, the best time complexity you can expect for graph algorithms is . The time required to access each vertex and each edge exactly one time. An algorithm whose time complexity is is sometimes referred to as linear in the size of .