274
个编辑
更改
跳到导航
跳到搜索
第229行：
第229行： − 也可以使用邻接表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻居是无序的，测试边的存在可以按照给定顶点的最小度成比例的时间进行，通过使用一个线性搜索通过这个顶点的邻居。如果邻居被表示为一个排序数组，二进制搜索可以代替，采取时间成正比的对数度。+
→Operations
It is also possible, but not as efficient, to use adjacency lists to test whether an edge exists or does not exist between two specified vertices. In an adjacency list in which the neighbors of each vertex are unsorted, testing for the existence of an edge may be performed in time proportional to the minimum degree of the two given vertices, by using a sequential search through the neighbors of this vertex. If the neighbors are represented as a sorted array, binary search may be used instead, taking time proportional to the logarithm of the degree.
It is also possible, but not as efficient, to use adjacency lists to test whether an edge exists or does not exist between two specified vertices. In an adjacency list in which the neighbors of each vertex are unsorted, testing for the existence of an edge may be performed in time proportional to the minimum degree of the two given vertices, by using a sequential search through the neighbors of this vertex. If the neighbors are represented as a sorted array, binary search may be used instead, taking time proportional to the logarithm of the degree.
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。
==Trade-offs==
==Trade-offs==