使用 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 documentation中给出的示例中的关键行：

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

改用bfs_edge，例如via 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 ,[]) 习惯用法使列表变平，但是是二次的。关于 How to make a flat list out of a list of lists.

的讨论

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

Using networkx bfs_tree to obtain a list of nodes of a directed graph in BFS order

python

graph

networkx

breadth-first-search