Section 7.5 An Adjacency List
A more space-efficient way to implement a sparsely connected graph is to use an adjacency list. In an adjacency list implementation, we keep a master list of all the vertices in the
Graph
object, and each vertex object in the graph maintains a list of the other vertices that it is connected to. In our implementation of the Vertex
class we will use a dictionary rather than a list, where the dictionary keys are the vertices and the values are the weights. Figure 7.5.1 illustrates the adjacency list representation for the graph in Section 7.2.![](external/Graphs/Figures/adjlist.png)
The advantage of the adjacency list implementation is that it allows us to compactly represent a sparse graph. The adjacency list also allows us to easily find all the links that are directly connected to a particular vertex.
You have attempted of activities on this page.