python - NetworkX 在有向图中查找特定节点的 root_node

Question

假设我在网络 X 中有一个有向图 G:

1. G中有多棵树
2. G 中的每个节点 N 恰好有 1 或 0 parent 的。

对于特定节点 N1，我想找到它所在树的根节点(它的度数为 0 的祖先)。在网络 x 中是否有一种简单的方法可以做到这一点？

我看了: Getting the root (head) of a DiGraph in networkx (Python) 但是我的图中有多个根节点。只有一个根节点恰好与 N1 在同一棵树中。

Answer 1

edit Nov 2017 请注意，这是在 networkx 2.0 发布之前编写的。有一个 migration guide用于将 1.x 代码更新为 2.0 代码(特别是使其与两者兼容)

---

这是一个简单的递归算法。它假定最多只有一个单亲。如果某物没有 parent ，它就是根。否则，它返回其父级的根。

def find_root(G,node):
    if G.predecessors(node):  #True if there is a predecessor, False otherwise
        root = find_root(G,G.predecessors(node)[0])
    else:
        root = node
    return root

如果图是有向无环图，它仍然会找到一个根，尽管它可能不是唯一的根，甚至可能不是给定节点的唯一根祖先。