7,129
个编辑
更改
跳到导航
跳到搜索
第51行：
第51行： − + − 第58行：
第57行： − +
→数据结构
==数据结构==
==数据结构==
作为一种数据结构，邻接表的主要替代是邻接矩阵。因为邻接矩阵中的每个项只需要一个位，它可以用一种非常紧凑的方式表示，只占用|V|2/8字节的连续空间，其中|V|是图的顶点数。除了避免浪费空间之外，这种紧凑性还支持'''<font color="#ff8000">局部引用 locality of reference</font>'''。
'''<font color="32CD32">作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特 bit ，所以它可以用非常紧凑的方式表示，只占用相邻空间的|V|2/8 字节，其中|V|是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用 locality of reference。</font>'''
注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V 2边(允许循环)，我们可以让''d ''= |E|/|V|2表示该图的密度。然后，8|E| > |V|2/8当|E|/|V|2 > 1/64时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V 2边(允许循环)，我们可以让''d ''= |E|/|V|2表示该图的密度。然后，当|E|/|V|2 > 1/64时，8|E| > |V|2/8 ,即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。