274
个编辑
更改
跳到导航
跳到搜索
第271行：
第271行： − + 第279行：
第279行： − 除了空间上的权衡，不同的数据结构也促进了不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。是否有一个给定的顶点之间的边可以确定与一个邻接矩阵一次，而需要时间成正比的最小程度的两个顶点与邻接表。+
→Data structures
Noting that an undirected simple graph can have at most <sup>2</sup>-)/2 ≈ V<sup> 2</sup>}} edges, allowing loops, we can let /<sup>2</sup>}} denote the density of the graph. Then, > <sup>2</sup>/8}} when /<sup>2</sup> > 1/64}}, that is the adjacency list representation occupies more space than the adjacency matrix representation when . Thus a graph must be sparse enough to justify an adjacency list representation.
Noting that an undirected simple graph can have at most <sup>2</sup>-)/2 ≈ V<sup> 2</sup>}} edges, allowing loops, we can let /<sup>2</sup>}} denote the density of the graph. Then, > <sup>2</sup>/8}} when /<sup>2</sup> > 1/64}}, that is the adjacency list representation occupies more space than the adjacency matrix representation when . Thus a graph must be sparse enough to justify an adjacency list representation.
注意到一个无向简单图最多可以有 < sup > 2 </sup > -)/2≈ v < sup > 2 </sup > }边，允许循环，我们可以让/< sup > 2 </sup > }表示该图的密度。然后，> < sup > 2 </sup >/8}当/< sup > 2 </sup > > 1/64}时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，以证明邻接表表示。
注意到一个无向简单图最多可以有 < sup > 2 </sup > -)/2≈ v < sup > 2 </sup > }边，允许循环，我们可以让/< sup > 2 </sup > }表示该图的密度。然后，> < sup > 2 </sup >/8}当/< sup > 2 </sup > > 1/64}时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
Besides the space trade-off, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list. With an adjacency matrix, an entire row must instead be scanned, which takes )}} time. Whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list.
Besides the space trade-off, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list. With an adjacency matrix, an entire row must instead be scanned, which takes )}} time. Whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list.
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
==References==
==References==