查找有向图中的所有根(networkx)

2024-03-29 12:32:38 发布

您现在位置:Python中文网/ 问答频道 /正文

假设我有创建有向图的代码:

dict = {1:['a1', 'a2', 'a3'], 2:['a4', 'a5','a7']}
graph = nx.from_dict_of_lists(dict)
digraph = nx.DiGraph(graph)

我如何在这个图中找到所有的根? 此图的预期输出为[1,2]

如果对您更方便的话,我已经在一个google colab notebook中编写了代码,您可以在其中看到图形,希望能有所帮助

编辑:这与这个question有某种关系。区别在于,在那篇文章中,有一个假设,即图是连通的,因此只有一个根;我的例子不是这样的。 我可以将我的图“划分”为连接的子图,然后在每个子图中搜索根吗


Tags: of代码froma2a1dictlistsa3
0条回答
网友
1楼 · 发布于 2024-03-29 12:32:38

我认为您在这个示例中并没有完全生成您心目中的图形,因为所有存在的连接都有双向边。可能您打算生成图形:

d = {1:['a1', 'a2', 'a3'], 2:['a4', 'a5','a7']}
G = nx.from_dict_of_lists(d, create_using=nx.DiGraph)
print(graph.edges())
# OutEdgeView([('1', 'a1'), ('1', 'a2'), ('1', 'a3'), ('2', 'a4'), ('2', 'a5'), ('2', 'a7')])

它给出了两个分量图:

plt.subplots(figsize=(12,6))
nx.draw(G, with_labels=True, node_color='lightblue', node_size=500)

enter image description here

为了找到每个组件中的根节点,我们首先需要从现有的连接组件生成诱导子图,因为我们有^{}。然后,在每个子图上,通过在所有节点上搜索,并保持一个子图的^{}0,可以找到根节点

roots = []
for component in nx.weakly_connected_components(G):
    G_sub = G.subgraph(component)
    roots.extend([n for n,d in G_sub.in_degree() if d==0])

其中:

print(roots)
# [1, 2]

相关问题 更多 >