在networkx（Python）中获取有向图的根（头部）

Question

我在一个项目中试图使用networkx进行一些图形表示，但不确定如何完成几个看似简单的任务。我创建了一个有许多节点和边的有向图，其中只有一个根元素。现在，我想从根开始遍历每个元素的子节点，并从它们中提取一些信息。如何获取这个DiGraph的根元素？

所以代码大概是这样的：

#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)，希望它从根节点开始迭代，但顺序似乎是随机的... :\

希望能得到帮助，谢谢！

- mindthief

---

在我不太了解的情况下，一个图并不一定有根节点，因此也就没有找到它的函数。 - fmark

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]

另一种方法是从给定的（随机）节点开始，沿着前任节点跟踪，直到找到没有前任节点的节点为止，这可能更快。

- Aric

---

我尝试了拓扑排序，它有效了。速度对于这个操作来说不是主要问题，所以我可能会坚持使用它，但如果速度成为问题，我会考虑你的第三个选项。 - mindthief

我尝试了，但出现了错误 'DiGraph' object has no attribute 'in_degree'。是 networkx 废弃或修改了 in_degree() 方法吗？你能否发布你使用的 networkx 版本？ - Yossarian42

in_degree() 在我使用 DiGraph 时有效。我正在使用 networkx 版本 2.2。 - Marco