图邻接列表不同实现的优缺点

Question

我见过一个图的邻接列表的多个表示形式，我不知道该使用哪一个。

1. 我正在考虑节点对象和图形对象的以下表示形式(如下所示(

class Node(object):
def __init__(self, val):
self.val = val
self.connections_distance = {}
# key = node: val = distance
def add(self, neighborNode, distance):
if neighborNode not in self.connections_distance:
self.connections_distance[neighborNode] = distance
class Graph(object):
def __init__(self):
self.nodes = {}
# key = node.val : val = node object
# multiple methods

2. 第二种方法是节点标记为 0 - n - 1(n 是节点数(。每个节点将其邻接存储为链表数组(其中索引是节点值，链表存储其所有邻居(

例如图表：

0 连接到 1 和 2
1 连接到 0 和 2
2 连接到 0 和 1

或者，如果 [a， b， c] 是包含 a、b 和 c 的数组，并且 [x -> y -> z] 是包含 x、y 和 z 的链表：

表示：[[1->2], [0->2], [0->1]]

问题：每种表示的优缺点是什么，哪个使用更广泛？

Answer 1

注意：一个表示包括距离而另一个没有，这有点奇怪。他们很容易都包含距离或都省略它们，所以我会省略该细节(您可能对set()而不是{}感兴趣(。

看起来这两种表示都是邻接列表的变体(在 https://stackoverflow.com/a/62684297/3798897 中进一步解释(。从概念上讲，这两种表示形式之间没有太大区别 - 您有一个节点集合，每个节点都有一个对邻居集合的引用。你的问题实际上是两个独立的问题：

(1(你应该使用字典还是数组来保存节点的集合？

• 它们几乎是等价的;字典只不过是幕后的一个数组。如果您没有充分的理由这样做，那么依靠内置字典而不是使用您自己的哈希函数和密集数组重新实现字典可能是正确的选择。
• 字典将使用更多空间
• 从字典中删除字典会快得多(如果您实际上指的是数组而不是 python 的列表，插入也会更快(
• 如果你有一种快速的方法为每个节点生成数字 1-n，那么这可能比字典在幕后使用的哈希函数效果更好，所以你可能想要使用数组。

(2(你应该使用集合还是链表来保存相邻节点的集合？

• 几乎可以肯定你想要一套。它至少在渐近上与您想要对邻居集合执行的任何操作的列表一样好，它对缓存更友好，对象开销更少，等等。

与往常一样，您的特定问题可能会以一种或另一种方式影响选择。 例如，我提到数组的插入/删除性能比字典差，但如果你几乎从不插入/删除，那也没关系，稍微减少的内存会开始看起来很有吸引力。