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 的数量节点）。将边添加到网络通常需要 linear 时间以及 O(n) 在 number您添加的边，对于单个边来说如此恒定，但在（非常）不太可能的情况下可能需要二次时间 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 class 允许使用 G['a']:

访问子词典

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

AtlasView 是一种字典视图，可防止编辑基础字典。

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

NetworkX g.neighbors(n) time complexity

python

graph-theory

networkx