向无权有向图中添加边有效率吗？

Question

我有三个用python字典表示的图

A: {1:[2], 2:[1,3], 3:[]}. 

B: {1: {neighbours:[2]}, 2: {neighbours:[1,3]}, 3: {neighbours:[]}}

C: {1: {2:None}, 2: {1:None, 3:None}, 3: {}}

我有一个hasEdge和addEdge函数

def addEdge(self, source, target):

assert self.hasNode(source) and self.hasNode(target)
if not self.hasEdge(source, target):
    self.graph[source][target] = None

def hasEdge(self, source, target):

    assert self.hasNode(source) and self.hasNode(target)
    return target in self.graph[source]

我不确定哪个结构对每个函数最有效，我的直接想法是第一个结构对添加边最有效，如果有边，C结构对返回最有效

Answer 1

对我来说，C似乎是最有效的，因为您所做的查找平均为O（1）。（注意，这是平均情况，不是最坏情况。）对于邻接列表，您可以使用最坏情况线性搜索。你知道吗

对于稀疏图，您可能希望使用邻接列表（a），因为它们占用的空间较少。然而，对于稠密图，选项C应该是最有效的。你知道吗

A和B将有非常相似的运行时-渐近相同。除非您希望将邻居之外的数据添加到这些节点，否则我将选择A

我不熟悉python；但是，对于Java，可以通过使用HashSet（set）来改进选项C，这将减少您的空间需求。运行时与使用HashMap相同，但集合不存储值-仅存储键，这是检查两个节点之间是否存在边所需的。你知道吗

所以，澄清一下：

对于运行时，选择C。您将有平均情况O（1）边缘添加。为了改进C语言以减少内存消耗，可以使用集合而不是映射，这样就不必为值分配空间。你知道吗

对于内存，如果有稀疏图，请选择一个。您将节省大量内存，并且在运行时方面不会损失太多。作为参考，稀疏是指节点没有太多邻居的情况；例如，在一个有20个节点的图中，每个节点大约有2个邻居。你知道吗

Answer 2

A和B是经典的邻接列表。C是一个邻接列表，但是使用O(1)结构而不是O(N)结构作为列表。但实际上，您应该使用D，即邻接集。你知道吗

在Python中，set.contains(s)是一个O(1)操作。你知道吗

所以我们可以

graph = { 1: set([2]), 2: set([1, 3], 3: set() }

那么我们的addEdge(from, to)就是

graph[from].add(to)
graph[to].add(from)

我们的hasEdge(from,to)只是

to in graph[from]