7,129
个编辑
更改
跳到导航
跳到搜索
第20行：
第20行： − * 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>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。 − + − Goodrich和Tamassia提出的[[面向对象]]入射列表结构有特殊的顶点对象和边缘对象类。每个顶点对象都有一个实例变量，指向一个集合对象，该集合对象列出了邻近的边缘对象。反过来，每个边缘对象又指向其端点的两个顶点对象。<ref name="A">{{cite book| author = Michael T. Goodrich and Roberto Tamassia | title = Algorithm Design: + − − 这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。 第43行：
第37行： − 也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。+ 第49行：
第43行： − + − + 第58行：
第52行： − + − 用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用8e字节的存储空间，其中e表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。+ − + 第70行：
第64行： +
→实现
图的邻接表表示法将图中的每个顶点与其邻接顶点或边的集合关联起来。这个基本思想有许多变体，在如何实现顶点和集合之间的关联，如何实现集合，以及是否包括顶点和边还是只包括顶点作为第一类对象，以及什么类型的对象被用来表示顶点和边的细节上都有所不同。
图的邻接表表示法将图中的每个顶点与其邻接顶点或边的集合关联起来。这个基本思想有许多变体，在如何实现顶点和集合之间的关联，如何实现集合，以及是否包括顶点和边还是只包括顶点作为第一类对象，以及什么类型的对象被用来表示顶点和边的细节上都有所不同。
* [[Guido van Rossum]]建议的实现方式是使用'''哈希表 hash table'''将图中的每个顶点与相邻顶点的数组数据结构联系起来。在这种表示方式中，一个顶点可以由任何可哈希的对象表示，没有明确地将边表示为对象。<ref>{{cite web| author = Guido van Rossum| year = 1998| title = Python Patterns - Implementing Graphs| url = https://www.python.org/doc/essays/graphs/}}</ref>。
*Cormen等人提出了一种用索引号来表示顶点的实现方法。<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>他们的表示方法是使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的'''单链表 singly linked list'''。在这种表示方式中，单链表的节点可以解释为边对象；然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<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.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: Foundations, Analysis, and Internet Examples| publisher = John Wiley & Sons | year = 2002 | isbn = 0-471-38365-1}}</ref> 这种表示方式邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
<br>
<br>
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行'''<font color="#ff8000">顺序搜索 sequential search</font>'''，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用'''<font color="#ff8000">二分搜索法 binary search</font>'''，时间与次数的对数成正比。
<br>
<br>
'''<font color="#ff8000">邻接表</font>'''的主要替代方法是'''<font color="#ff8000">邻接矩阵 Adjacency Matrix </font>'''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''<font color="#ff8000">稀疏图 Sparse Graph </font>'''（大多数顶点对不是由边连接的图），'''<font color="#ff8000">邻接表</font>'''比邻接矩阵（存储为二维数组）更节省空间：'''<font color="#ff8000">邻接表</font>'''的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的'''<font color="#ff8000">哈希表</font>'''而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配'''<font color="#ff8000">邻接表</font>'''的线性空间使用。
'''邻接表'''的主要替代方法是'''[[邻接矩阵 Adjacency Matrix]]'''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''<font color="#ff8000">稀疏图 Sparse Graph </font>'''（大多数顶点对不是由边连接的图），邻接表比邻接矩阵（存储为二维数组）更节省空间：邻接表的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的哈希表而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配邻接表的线性空间使用。
'''<font color="#ff8000">邻接表</font>'''和'''<font color="#ff8000">邻接矩阵</font>'''之间的另一个显著区别是它们执行操作的效率。在'''<font color="#ff8000">邻接表</font>'''中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在'''<font color="#ff8000">邻接矩阵</font>'''中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，'''<font color="#ff8000">邻接矩阵</font>'''允许测试两个顶点是否在固定的时间内彼此相邻; '''<font color="#ff8000">邻接表</font>'''支持这一操作的速度较慢。
'''邻接表'''和'''邻接矩阵'''之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。此外，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻；邻接表支持这一操作的速度较慢。
<br>
<br>
'''<font color="32CD32">作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的n<sup>2</sup>/8}}字节，其中n是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用locality of reference。</font>'''
'''<font color="32CD32">作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特 bit ，所以它可以用非常紧凑的方式表示，只占用相邻空间的|V|2/8 {{math|{{abs|''V''}}<sup>2</sup>/8}}字节，其中n是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用 locality of reference。</font>'''
用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用 |V|2/8字节的存储空间，其中e表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。
注意到一个'''<font color="#ff8000">无向简单图</font>'''最多可以有 n<sup>2</sup>边(允许循环)，我们可以让d=e/n<sup>2</sup>表示该图的密度。然后，8e>n<sup>2</sup>/8当d>1/64时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
注意到一个'''无向简单图'''最多可以有 n<sup>2</sup>边(允许循环)，我们可以让d=e/n<sup>2</sup>表示该图的密度。然后，8e>n<sup>2</sup>/8当d>1/64时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
<br>
<br>
==参考资料==
==参考资料==