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

Question

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

这是优点，我能想到。

作为 Set 属性，该图可以在重复边和 的许多其他属性方面提供保证。套装 .此外所有设置操作来自 Set Theory变得可用，从而更直观地处理分析。如:

vertex_set_A | vertex_setB是联合操作。

vertex_set_A & vertex_set_B , 是相交运算。

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

在性能方面，可以使用 HashSet 实现，这将提供恒定时间操作。或者 TreeSet 当图形需要在日志时间操作上频繁动态更改时。

列表数据结构还维护元素的排序属性，这在大多数图中没有用处。事实上，列表以有序的方式迭代，这首先不应该发生。 Indexed Ordered 应该无关紧要，Set 可以提供。排序重要的唯一时间是图形加权时，因此基于权重的排序，其中 TreeSet 主要在日志时间操作中运行。

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

Answer 1

这确实是一个很好的问题，事实上，没有一个全面的答案，只是再次重复这个问题，“为什么不”确实如此。
评论中的原因在我看来更像是凑合的借口，因为这只是历史上一直存在的，仍然不足以保证真正的原因。
List 只是一个通用标签，如果集合更适合您的任务，您可以(并且应该)使用它。
有些人会争辩说该集合不能为您提供保证的 O(1) 查找时间 - 它已摊销，并且即使非常不可能，最坏的情况仍然是 O(n)，其他人会通过列表推理更快的迭代，然后是关于实现可行性的争论。
虽然它们在技术上没有错，但我并不真正相信其中任何一个是主要原因。我觉得真正的原因是它们被使用了 '只是因为约定' . 一般的标签是“列表”，它的字面意思已经足够频繁，以至于失去了它的通用性。
如果您的应用程序适合它，当然可以继续使用集合。
我的教科书也使用了它们。
(哦，还有一个例子，当我说“应用程序借给它自己”时，它会驱动那个回家；如果您需要在应用程序中经常找到入度，该集合将为您提供 O(V) 运行时，其中 V 表示顶点数，邻接列表将为您提供 O(E) 运行时间，其中 E 表示边数。对于密集图，假设不允许平行边，O(E) 往往会变为 O(V^2)。因此，邻接集会给您一个更好的运行时性能在这里。)