7,129
个编辑
更改
跳到导航
跳到搜索
第52行：
第52行： − + − + − + − +
→数据结构
'''<font color="32CD32">作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特 bit ，所以它可以用非常紧凑的方式表示，只占用相邻空间的|V|2/8 {{math|{{abs|''V''}}<sup>2</sup>/8}}字节，其中n是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用 locality of reference。</font>'''
'''<font color="32CD32">作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特 bit ，所以它可以用非常紧凑的方式表示，只占用相邻空间的|V|2/8 字节，其中|V|是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用 locality of reference。</font>'''
用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用 |V|2/8字节的存储空间，其中e表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。
用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用 2·(32/8)|E| = 8|E| 字节的存储空间，其中|E|表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。
注意到一个'''无向简单图'''最多可以有 n<sup>2</sup>边(允许循环)，我们可以让d=e/n<sup>2</sup>表示该图的密度。然后，8e>n<sup>2</sup>/8当d>1/64时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V 2边(允许循环)，我们可以让''d ''= |E|/|V|2表示该图的密度。然后，8|E| > |V|2/8当|E|/|V|2 > 1/64时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费O(n)的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费O(|V|) 的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
<br>
<br>