假设我有创建有向图的代码:
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有某种关系。区别在于,在那篇文章中,有一个假设,即图是连通的,因此只有一个根;我的例子不是这样的。 我可以将我的图“划分”为连接的子图,然后在每个子图中搜索根吗
我认为您在这个示例中并没有完全生成您心目中的图形,因为所有存在的连接都有双向边。可能您打算生成图形:
它给出了两个分量图:
为了找到每个组件中的根节点,我们首先需要从现有的连接组件生成诱导子图,因为我们有^{} 。然后,在每个子图上,通过在所有节点上搜索,并保持一个子图的^{} 为
0
,可以找到根节点其中:
相关问题 更多 >
编程相关推荐