Skip to content

Latest commit

 

History

History
8 lines (5 loc) · 662 Bytes

File metadata and controls

8 lines (5 loc) · 662 Bytes

7.5.邻接表

实现稀疏连接图的更空间高效的方法是使用邻接表。在邻接表实现中,我们保存Graph 对象中的所有顶点的主列表,然后图中的每个顶点对象维护连接到的其他顶点的列表。 在我们的顶点类的实现中,我们将使用字典而不是列表,其中字典键是顶点,值是权重。 Figure 4 展示了 Figure 2中的图的邻接列表示。 7.5.邻接表.figure4

Figure 4

邻接表实现的优点是它允许我们紧凑地表示稀疏图。 邻接表还允许我们容易找到直接连接到特定顶点的所有链接。