274
个编辑
更改
跳到导航
跳到搜索
第247行：
第247行： − + − 作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只需要一个位，所以它可以以非常紧凑的方式表示，只占用连续空间的 < sup > 2 </sup >/8}字节，其中}}是图的顶点数。除了避免浪费空间，这种紧凑性鼓励访问局部性。+ 第277行：
第277行： − −
→Data structures
==Data structures==
==Data structures==
数据结构
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only {{math|{{abs|''V''}}<sup>2</sup>/8}} bytes of contiguous space, where {{math|{{abs|''V''}}}} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only {{math|{{abs|''V''}}<sup>2</sup>/8}} bytes of contiguous space, where {{math|{{abs|''V''}}}} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only <sup>2</sup>/8}} bytes of contiguous space, where }} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only <sup>2</sup>/8}} bytes of contiguous space, where }} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只需要一位，所以它可以用非常紧凑的方式表示图，只占用连续空间的 < sup > 2 </sup >/8}字节，其中}}是图的顶点数。除了避免浪费空间，这种紧凑性鼓励访问局部性。
除了空间上的权衡，不同的数据结构也促进了不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。是否有一个给定的顶点之间的边可以确定与一个邻接矩阵一次，而需要时间成正比的最小程度的两个顶点与邻接表。
除了空间上的权衡，不同的数据结构也促进了不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。是否有一个给定的顶点之间的边可以确定与一个邻接矩阵一次，而需要时间成正比的最小程度的两个顶点与邻接表。
==References==
==References==