获取networkx中有向图的根节点

Question

我在一个项目中想用 networkx 来做图的表示，但有些事情我不太确定怎么做，明明应该很简单。我创建了一个有向图，里面有很多节点和边，确保这个图里只有一个根节点。现在，我想从根节点开始，遍历每个元素的子节点，并从中提取一些信息。我该怎么获取这个有向图的根节点呢？

大概是这样的：

#This is NOT real code, just pseudopython to convey the general intent of what I'd like to do

    root = myDiGraph.root()
    for child in root.children():
        iterateThroughChildren(child)

def iterateThroughChildren(parent):
    if parent.hasNoChildren(): return
    for child in parent.children():
        //do something
        //
        iterateThroughChildren(child)

我在文档里没看到有什么简单的方法可以获取有向图的根节点——难道我得手动推断吗？:O 我试着用 iter(myDiGraph) 来获取节点，希望它能从根节点开始遍历，但顺序看起来是随机的... :\

如果能得到帮助，我会很感激，谢谢！

Answer 1

如果你说的“一个根元素”是指你的有向图是一个根树，那么根节点就是唯一一个入度为零的节点。

你可以用线性时间（根据节点数量）找到这个节点，方法是：

In [1]: import networkx as nx

In [2]: G=nx.balanced_tree(2,3,create_using=nx.DiGraph()) # tree rooted at 0

In [3]: [n for n,d in G.in_degree() if d==0] 
Out[3]: [0]

或者你也可以使用拓扑排序（根节点是第一个元素）：

In [4]: nx.topological_sort(G)
Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]

另外，从一个给定的（随机的）节点开始，沿着前驱节点查找，直到找到一个没有前驱的节点，可能会更快。