29
个编辑
更改
无编辑摘要
* An implementation suggested by [[Guido van Rossum]] uses a [[hash table]] to associate each vertex in a graph with an [[array data structure|array]] of adjacent vertices. In this representation, a vertex may be represented by any hashable object. There is no explicit representation of edges as objects.<ref>{{cite web
* An implementation suggested by [[Guido van Rossum]] uses a [[hash table]] to associate each vertex in a graph with an [[array data structure|array]] of adjacent vertices. In this representation, a vertex may be represented by any hashable object. There is no explicit representation of edges as objects.<ref>{{cite web
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】吉多·范罗苏姆（Guido van Rossum）提出一种实现方法：'''<font color="#ff8000">哈希表</font>'''，将图中的每个顶点与其相邻顶点采用一种'''<font color="#ff8000">数组</font>'''数据结构表示。在这种表示法中，顶点可以由任何散列对象表示，而连边没有被表示为对象。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】* 吉多·范罗苏姆（Guido van Rossum）提出一种实现方法：'''<font color="#ff8000">哈希表</font>'''，将图中的每个顶点与其相邻顶点采用一种'''<font color="#ff8000">数组</font>'''数据结构表示。在这种表示法中，顶点可以由任何散列对象表示，而连边没有被表示为对象。
| author = [[Guido van Rossum]]
| author = [[Guido van Rossum]]
| title = Python Patterns ーー实现图形
| title = Python Patterns ーー实现图形
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“| title = Python Patterns ーー实现图形”改为“标题 = Python代码 --图形实现”
| url = https://www.python.org/doc/essays/graphs/}}</ref>
| url = https://www.python.org/doc/essays/graphs/}}</ref>
* Cormen et al. suggest an implementation in which the vertices are represented by index numbers.<ref>{{cite book
* Cormen et al. suggest an implementation in which the vertices are represented by index numbers.<ref>{{cite book
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】Cormen等建议使用'''<font color="#ff8000">顶点索引号</font>'''对顶点操作
| title = [[Introduction to Algorithms]], Second Edition
| title = [[Introduction to Algorithms]], Second Edition
算法导论，第二版
算法导论，第二版
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】|标题 = 《算法导论》，第二版
| publisher = MIT Press and McGraw-Hill
| publisher = MIT Press and McGraw-Hill
| publisher = MIT Press and McGraw-Hill
| publisher = MIT Press and McGraw-Hill
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】|出版社 = MIT Press and McGraw-Hill
| year = 2001
| year = 2001
|author1 = Thomas H. Cormen|author2 = Charles E. Leiserson| author3 = Ronald L. Rivest
|author1 = Thomas H. Cormen|author2 = Charles E. Leiserson| author3 = Ronald L. Rivest
|author1 = 托马斯·科尔曼 | author2 = 查尔斯·雷瑟尔森 | author3 = 罗纳德·李维斯特
| author4 = Clifford Stein
| author4 = Clifford Stein
| author4 = Clifford Stein
| author4 = Clifford Stein
|author4 = Clifford Stein
| authorlink1 = Thomas H. Cormen
| authorlink1 = Thomas H. Cormen
| authorlink1 = Thomas H. Cormen
| authorlink1 = Thomas H. Cormen
|authorlink1 = 托马斯·科尔曼
| authorlink2 = Charles E. Leiserson
| authorlink2 = Charles E. Leiserson
| authorlink2 = Charles E. Leiserson
| authorlink2 = Charles E. Leiserson
|authorlink2 = 查尔斯·雷瑟尔森
| authorlink3 = Ronald L. Rivest
| authorlink3 = Ronald L. Rivest
| authorlink3 = Ronald L. Rivest
| authorlink3 = Ronald L. Rivest
|authorlink3 = 罗纳德·李维斯特
| authorlink4 = Clifford Stein
| authorlink4 = Clifford Stein
| authorlink4 = Clifford Stein
| authorlink4 = Clifford Stein
| authorlink4 = Clifford Stein
}}</ref> Their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a [[singly linked list]] of the neighboring vertices of that vertex. In this representation, the nodes of the singly linked list may be interpreted as edge objects; however, they do not store the full information about each edge (they only store one of the two endpoints of the edge) and in undirected graphs there will be two different linked list nodes for each edge (one within the lists for each of the two endpoints of the edge).
}}</ref> Their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a [[singly linked list]] of the neighboring vertices of that vertex. In this representation, the nodes of the singly linked list may be interpreted as edge objects; however, they do not store the full information about each edge (they only store one of the two endpoints of the edge) and in undirected graphs there will be two different linked list nodes for each edge (one within the lists for each of the two endpoints of the edge).
} </ref > 它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<font color="#ff8000">无向图 Undirected Graph </font>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。
} </ref > 它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<font color="#ff8000">无向图 Undirected Graph </font>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】删除“} </ref >”
*The [[object oriented]] incidence list structure suggested by Goodrich and Tamassia has special classes of vertex objects and edge objects. Each vertex object has an instance variable pointing to a collection object that lists the neighboring edge objects. In turn, each edge object points to the two vertex objects at its endpoints.<ref name="A">{{cite book
*The [[object oriented]] incidence list structure suggested by Goodrich and Tamassia has special classes of vertex objects and edge objects. Each vertex object has an instance variable pointing to a collection object that lists the neighboring edge objects. In turn, each edge object points to the two vertex objects at its endpoints.<ref name="A">{{cite book
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】Goodrich & Tamassia提出的'''<font color="#ff8000">面向对象</font>'''关联列表结构具有特殊类的顶点对象和边对象。每个顶点对象都有一个实例变量，指向列出相邻边对象的集合对象。反过来，每个边对象都指向其端点处的两个顶点对象。
| author = [[Michael T. Goodrich]] and [[Roberto Tamassia]]
| author = [[Michael T. Goodrich]] and [[Roberto Tamassia]]
| author = Michael T. Goodrich and Roberto Tamassia
| author = Michael T. Goodrich and Roberto Tamassia
作者: Michael t. Goodrich and Roberto Tamassia
| 作者: Michael t. Goodrich and Roberto Tamassia
| title = Algorithm Design: Foundations, Analysis, and Internet Examples
| title = Algorithm Design: Foundations, Analysis, and Internet Examples
| title = Algorithm Design: Foundations, Analysis, and Internet Examples
| title = Algorithm Design: Foundations, Analysis, and Internet Examples
| title = 算法设计: 基础、分析和互联网示例
| title = 算法设计: 基础、分析和互联网示例
| publisher = John Wiley & Sons
| publisher = John Wiley & Sons
| publisher = John Wiley & Sons
| publisher = John Wiley & Sons
| publisher = 约翰威立
| year = 2002
| year = 2002
| year = 2002
| year = 2002
2002年
| 2002年
| isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.
| isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.
| isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.
| isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.
| 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''.