python-3.x - 使用 NetworkX 查找图中每个节点的根

Question

如何使用 NetworkX 为图中的每个节点获取根？

这是我的图表示例：

预期结果：

节点 4 有根：0

节点 2 有根：0

节点 1 有根：0

节点 0 有根：0

节点 3 有根：8

节点 5 有根：8

节点 8 有根：8

我创建了一个while循环来获取节点的根，它运行良好，除非它非常慢。

对于大型网络，有什么有效的方法可以做到这一点吗？

标签： python-3.xgraphnetworkxgraph-theory

Answer 1

假设每个组件有一个根节点，您可以首先查找图中的所有根节点，检查哪些节点的度数为0。一旦确定，遍历nx.weakly_connected_components，并找到属于它的根节点：

roots = {n for n,d in G.in_degree() if d==0}
d = {}
for comp in nx.weakly_connected_components(G):
    comp_root = next(root for root in roots if root in comp)
    d.update(dict.fromkeys(comp, comp_root))  

---

print(d)
{0: 0, 1: 0, 2: 0, 4: 0, 8: 8, 3: 8, 5: 8}