使用 NetworkX 查找图中每个节点的根

Question

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

这是我的图表示例：

预期结果：

节点 4 有根：0

节点 2 有根：0

节点 1 有根：0

节点 0 有根：0

节点 3 有根：8

节点 5 有根：8

节点 8 有根：8

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

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

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}