python - NetworkX g.neighbors(n) 时间复杂度

Question

获取networkx中节点的邻居的时间复杂度是多少？

>>> G = nx.Graph()
>>> G.add_edges_from([('a', 'b'), ('a', 'c')])
>>> G.neighbors('a')

Answer 1

简短回答:获取邻居需要线性时间O(m)(其中m邻居数量，或者在不太可能的情况下 O(m+n)，其中 n 节点数)。向网络添加边通常需要线性时间，并且在您添加的边数量中也需要O(n)，因此对于单边，但在(非常)不可能的情况下可能需要二次时间O(n²)。您可以使用“G['a'] 以恒定时间(在最坏情况下的线性时间)访问邻居字典。

我们可以检查 source code ，并查看:

def neighbors(self, n):
    # ...
    try:
        return list(self.adj[n])
    except KeyError:
        raise NetworkXError("The node %s is not in the graph." % (n,))

现在，如果检查源代码，我们会发现(默认情况下)adj 确实是一个字典:

node_dict_factory = dict
adjlist_dict_factory = dict
edge_attr_dict_factory = dict

def __init__(self, data=None, **attr):
    # ...
    self.node_dict_factory = ndf = self.node_dict_factory
    # ...
    self.node = ndf()  # empty node attribute dict
    # ...

因此，即使字典查找需要 - 最坏情况，但不太可能 - 节点数量的线性时间 O(n)，那么我们只有另一个线性时间来转换键列表进入列表。

另一方面，add_edges_from 方法的实现如下:

def add_edges_from(self, ebunch, attr_dict=None, **attr):
    # ...
    for e in ebunch:
        ne = len(e)
        if ne == 3:
            u, v, dd = e
        elif ne == 2:
            u, v = e
            dd = {}  # doesnt need edge_attr_dict_factory
        else:
            raise NetworkXError(
                "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,))
        if u not in self.node:
            self.adj[u] = self.adjlist_dict_factory()
            self.node[u] = {}
        if v not in self.node:
            self.adj[v] = self.adjlist_dict_factory()
            self.node[v] = {}
        datadict = self.adj[u].get(v, self.edge_attr_dict_factory())
        datadict.update(attr_dict)
        datadict.update(dd)
        self.adj[u][v] = datadict
        self.adj[v][u] = datadict

因此，我们基本上迭代列表中的每个项目，进行一些解包，然后将数据字典添加到 adj 两次(一次在一个方向，一次在另一个方向)。如果字典查找速度很快(通常是常数时间)，则该算法具有线性时间(以要添加的元组数量为单位)。最坏的情况(但可能性很小)字典查找可能需要线性时间，因此插入可以扩展到O(n²)。

然而，Graph 类允许使用 G['a'] 访问子词典:

>>> G['a']
AtlasView({'b': {}, 'c': {}})

AtlasView 是字典上的一个 View ，可防止人们编辑底层字典。