274
个编辑
更改
跳到导航
跳到搜索
第22行：
第22行： + + + − * Cormen et al. suggest an implementation in which the vertices are represented by index numbers.<ref>{{cite book| title = Introduction to Algorithms, Second Edition| publisher = MIT Press and McGraw-Hill | year = 2001|author1 = Thomas H. Cormen|author2 = Charles E. Leiserson| author3 = Ronald L. Rivest| author4 = 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). + +
→实现
* 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| author = Guido van Rossum| year = 1998| title = Python Patterns — Implementing Graphs| url = https://www.python.org/doc/essays/graphs/}}</ref>
* 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| author = Guido van Rossum| year = 1998| title = Python Patterns — Implementing Graphs| url = https://www.python.org/doc/essays/graphs/}}</ref>
由Guido van Rossum建议的一种实现方式使用哈希表将图中的每个顶点与相邻顶点的数组数据结构联系起来。在这种表示方式中，一个顶点可以由任何可哈希的对象表示，没有明确地将边表示为对象。<ref>{{cite web| author = Guido van Rossum| year = 1998| title = Python Patterns - Implementing Graphs| 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| title = Introduction to Algorithms, Second Edition| publisher = MIT Press and McGraw-Hill | year = 2001|author1 = Thomas H. Cormen|author2 = Charles E. Leiserson| author3 = Ronald L. Rivest| author4 = 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).
Cormen等人提出了一种用索引号来表示顶点的实现方法。Leiserson|作者3 = Ronald L. Rivest|作者4 = Clifford Stein }}</ref>他们的表示方法使用了一个按顶点编号索引的数组，其中每个顶点的数组单元指向该顶点的相邻顶点的[[单链列表]]。在这种表示方式中，单链表的节点可以被解释为边缘对象；但是，它们并不存储每个边缘的全部信息（它们只存储边缘两个端点中的一个），在非定向图中，每个边缘将有两个不同的链表节点（边缘两个端点中的每一个在列表中）。
它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<font color="#ff8000">无向图 Undirected Graph </font>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。
它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<font color="#ff8000">无向图 Undirected Graph </font>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。
*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| author = Michael T. Goodrich and Roberto Tamassia | title = Algorithm Design: Foundations, Analysis, and Internet Examples| publisher = John Wiley & Sons | year = 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.
*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| author = Michael T. Goodrich and Roberto Tamassia | title = Algorithm Design: Foundations, Analysis, and Internet Examples| publisher = John Wiley & Sons | year = 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.
Goodrich和Tamassia提出的[[面向对象]]入射列表结构有特殊的顶点对象和边缘对象类。每个顶点对象都有一个实例变量，指向一个集合对象，该集合对象列出了邻近的边缘对象。反过来，每个边缘对象又指向其端点的两个顶点对象。<ref name="A">{{cite book| author = Michael T. Goodrich and Roberto Tamassia | title = Algorithm Design:
这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。