时间戳

首页 > 解决方案 > 图邻接表不同实现方式的优缺点

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

问题描述

我已经看到了图的邻接列表的多种表示形式，但我不知道该使用哪一种。

  1. 我正在考虑 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
  1. 第二种方法是将节点标记为 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]]

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

标签： pythongraphadjacency-list

解决方案

注意：一个表示包含距离而另一个不包含距离有点奇怪。他们很容易同时包含距离或都省略它们，所以我会省略那个细节（你可能感兴趣set()而不是{}）。

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

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

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

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

  • 几乎可以肯定你想要一套。它至少在渐近上与你想对一组邻居做的任何事情的列表一样好，它对缓存更友好，它的对象开销更少，等等。

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

推荐阅读