更改

==数据结构==

==数据结构==

作为一种数据结构，邻接表的主要替代是邻接矩阵。因为邻接矩阵中的每个项只需要一个位，它可以用一种非常紧凑的方式表示，只占用<math>|V|^{2}/8</math>字节的连续空间，其中|V|是图的顶点数。除了避免浪费空间之外，这种紧凑性还支持'''<font color="#ff8000">局部引用 locality of reference</font>'''。

作为一种数据结构，邻接表的主要替代是邻接矩阵。因为邻接矩阵中的每个项只需要一个位，它可以用一种非常紧凑的方式表示，只占用<math>|V|^{2}/8</math>字节的连续空间，其中<math>|V|</math>是图的顶点数。除了避免浪费空间之外，这种紧凑性还支持'''<font color="#ff8000">局部引用 locality of reference</font>'''。

用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用 2·(32/8)|E| = 8|E| 字节的存储空间，其中|E|表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。

用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用<math> 2·(32/8)|E|= 8 |E|</math>字节的存储空间，其中<math>|E|</math>表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。

注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V ²边(允许循环)，我们可以让'' d ''= |E|/|V|2表示该图的密度。然后，当|E|/|V|2 > 1/64时，8|E| > |V|2/8 ,即当d = |E|/|V|2 ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。

注意到一个'''无向简单图'''最多可以有<math>（|V|^{2}-|V|）/2≈ V^{2}</math>条边(允许循环)，我们可以让<math>d = |E|/|V|^{2}}</math>表示该图的密度。然后，当<math>8|E| > |V|^{2}/8</math>时，<math>|E|/|V|^{2}} > 1/64</math>，即<math>d = |E|/|V|^{2}}>1/64</math> ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。