274
个编辑
更改
跳到导航
跳到搜索
第215行：
第215行： − + − + − 邻接表数据结构执行的主要操作是报告给定顶点的邻居列表。使用上面详细说明的任何实现，都可以在每个邻居的固定时间内执行。换句话说，报告一个顶点 v 所有邻居的总时间与 v 的度成正比。+ 第230行：
第230行： − −
→Operations
| isbn = 0-471-38365-1} </ref > 这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
| isbn = 0-471-38365-1} </ref > 这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
==Operations==
==Operations==<br>
操作
The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex. Using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the total time to report all of the neighbors of a vertex ''v'' is proportional to the [[degree (graph theory)|degree]] of ''v''.
The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex. Using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the total time to report all of the neighbors of a vertex ''v'' is proportional to the [[degree (graph theory)|degree]] of ''v''.
The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex. Using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the total time to report all of the neighbors of a vertex v is proportional to the degree of v.
The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex. Using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the total time to report all of the neighbors of a vertex v is proportional to the degree of v.
邻接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点''v''所有邻居的总时间与''v''的'''<font color="#ff8000">度 Degree 成正比。
也可以使用邻接表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻居是无序的，测试边的存在可以按照给定顶点的最小度成比例的时间进行，通过使用一个线性搜索通过这个顶点的邻居。如果邻居被表示为一个排序数组，二进制搜索可以代替，采取时间成正比的对数度。
也可以使用邻接表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻居是无序的，测试边的存在可以按照给定顶点的最小度成比例的时间进行，通过使用一个线性搜索通过这个顶点的邻居。如果邻居被表示为一个排序数组，二进制搜索可以代替，采取时间成正比的对数度。
==Trade-offs==
==Trade-offs==