为什么Graph adjacency不定义为邻接集，而是邻接表？

Question

在图论中，我们知道可以使用邻接表数据结构表示顶点邻接。相反，邻接集在图论的任何地方都没有被广泛提及。为什么呢？

这是优点，我能想到。

1. 作为 Set 属性，图可以在重复边和Set 的许多其他属性方面提供保证。而且从所有设置操作集理论面世哪个更直观与分析工作。如：

   • vertex_set_A | vertex_setB 是联合操作。
   • vertex_set_A & vertex_set_B, 是相交运算。

2. *观点，Set 更容易理解，因为它在数学证明中具有相关性。它还为低级代码如何处理数组和东西提供了一个很好的抽象。

3. 在性能方面，可以使用 HashSet 实现，这将提供恒定时间操作。或者 TreeSet 当图形需要在日志时间操作上频繁动态更改时。
4. 列表数据结构还维护元素的排序属性，这在大多数图中没有用处。事实上，列表以有序的方式迭代，这首先不应该发生。Indexed Ordered 应该无关紧要，Set 可以提供。排序重要的唯一时间是图形加权时，因此基于权重的排序，其中 TreeSet 主要在日志时间操作中运行。

所以，我不确定为什么大多数图算法只提到邻接表。是不是因为技术壁垒，Set更难实现，而List更容易？

Answer 1

这确实是一个非常好的问题，事实上，没有一个全面的答案，只是再次重复这个问题，“为什么不”。

对我来说，评论中的理由似乎更像是凑合的借口，因为这正是整个历史中存在的，但仍然不足以保证真正的理由。

列表只是一个通用标签，如果它更适合您的任务，您可以（并且应该）使用集合。

有些人会认为该集合不能为您提供有保证的 O(1) 查找时间 - 它是摊销的，即使可能性很小，最坏的情况仍然是 O(n)，其他人会通过列表推理更快的迭代，然后就是关于实施可行性的争论。

虽然从技术上讲它们并没有错，但我并不真正相信这些是主要原因。
我觉得真正的原因是它们被使用“只是因为惯例”。
一般标签是“列表”，而且人们经常按字面意思理解它，以至于失去了它的通用性。

如果您的应用程序适合的话，当然可以使用一套。
我的教科书也使用了它们。

（哦，当我说“应用程序借给它自己”时，举一个例子来说明这一点；如果您需要经常在应用程序中查找入度，则该集合将为您提供 O(V) 运行时间，其中 V 表示顶点数，邻接表将为您提供 O(E) 运行时间，其中 E 表示边数。对于密集图，假设不允许平行边，O(E) 往往会变为 O(V^2)。因此，邻接集将为您提供更好的运行时间此处的运行时性能。）