7.5. 邻接表¶
7.5. An Adjacency List
一种更节省空间的方式来实现稀疏连接的图是使用邻接表。在邻接表的实现中，我们维护一个包含所有顶点的主列表，每个图中的顶点对象维护一个与之连接的其他顶点的列表。在我们实现的 Vertex 类中，我们将使用字典而不是列表，其中字典的键是顶点，值是边的权重。Figure 4 说明了 Figure 2 图的邻接表表示。
邻接表实现的优点是它允许我们紧凑地表示一个稀疏图。邻接表还使我们能够轻松找到与特定顶点直接连接的所有链接。
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 4 illustrates the adjacency list representation for the graph in Figure 2.
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.
创建日期: 2024年9月9日