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

Question

我看到了一个图的邻接表的多种表示，但我不知道该使用哪一个。

我正在考虑 Node 对象和 Graph 对象的以下表示（如下所示）

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

第二种方式是将节点标记为 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() 而不是 {} 感兴趣）。

看起来这两种表示都是邻接列表的变体（在中进一步解释）。从概念上讲，这两种表示之间没有太大区别——您有一个节点集合，每个节点都有一个对邻居集合的引用。你的问题实际上是两个不同的问题：

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

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

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

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

一如既往，您的特定问题可能会影响您的选择。例如，我提到数组的 insertion/deletion 性能比字典差，但如果你几乎没有 insert/delete 那么那没关系，稍微减少的内存会开始看起来很有吸引力。

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

Pros and cons of different implementations of graph adjacency list

python

graph

adjacency-list