使用 networkx bfs_tree按 BFS 顺序获取有向图的节点列表

Question

例如，给定：

G = nx.DiGraph()
G.add_path([0, 1])
G.add_path([0, 2])
G.add_path([0, 3])
G.add_path([1, 11])
G.add_path([1, 12])
G.add_path([2, 21])
G.add_path([2, 22])
G.add_path([3, 31])
G.add_path([3, 32])

我想要这个： 0, 1, 2, 3, 11, 12, 21, 22, 31, 32

为什么bfs_tree的 networkx 文档在其示例中实际使用 bfs_edges？而不是bfs_tree？bfs_tree文档中给出的示例的关键行：

print(list(nx.bfs_edges(G,0))) 

改用bfs_edge，例如通过print(list(nx.algorithms.bfs_tree(G, 0).edges()))似乎会导致与示例代码返回的列表相同，但显然更复杂。我是否可以以更简单的方式使用bfs_tree()来获取按 BFS 顺序排列的有向图_nodes_列表？

当然，我可以迭代从bfs_tree或bfs_edges返回的列表，只采用第二个元素。但是没有更简单的方法吗？

Answer 1

为什么不扁平化边缘元组列表（每个 2 个节点），然后取节点set以确保唯一性？

list(set(sum(list(nx.algorithms.bfs_tree(G, 0).edges()), ())))

在假设的解决方案中，您将忽略0节点，并且它不会包含在您的输出中。

或者您可以使用 bfs_successors() 方法来获取节点的字典（传入0节点）并获取values。

[0].extend(nx.algorithms.bfs_successors(G, 0).values())
# Get your first, node, and extend with a list of all successor nodes in BFS order

Answer 2

从 Networkx 2.6.2 开始，这实际上有效：

[0] + [successor for successors in dict(nx.bfs_successors(G, 0)).values() for successor in successors]

<小时 />

编辑。 我最初的建议：

[0] + sum(dict(nx.bfs_successors(G, 0)).values(), [])

sum(l ,[])成语使列表扁平化，但是是二次的。讨论如何从列表列表中制作平面列表。