Networkx：按波遍历图形

Question

假设我在networkx中有一个下图

import networkx as nx

g = nx.Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(3, 1)
g.add_edge(4, 2)

所以它基本上是3-1-0-2-4线。你知道吗

有没有一种networkx方法可以通过“waves”执行BFS搜索？像这样：

for x in nx.awesome_bfs_by_waves_from_networkx(g, 0):
    print(x)
# should print
# [1, 2]
# [3, 4]

换句话说，我想找到所有的1环邻域，然后是2环，等等

我可以通过使用Queue来做到这一点，但是如果可能的话，我对使用networkx工具感兴趣。也可以使用具有不同depth_limit值的多个迭代器，但我希望可以找到更漂亮的方法。你知道吗

UPD：对于我来说，有一个不需要遍历整个图的惰性解决方案是很重要的，因为我的图可能很大，如果需要的话，我希望能够尽早停止遍历。你知道吗

Answer 1

您可以使用Dijkstra算法从0（或任何其他节点n）计算最短路径，然后按距离对节点进行分组：

from itertools import groupby
n = 0
distances = nx.shortest_paths.single_source_dijkstra(g, n)[0]
{node: [node1 for (node1, d) in y] for node,y 
                                   in groupby(distances.items(), 
                                              key=lambda x: x[1])}
#{0: [0], 1: [1, 2], 2: [3, 4]}

如果要按环进行（也称为壳），请使用邻域的概念：

core = set()
crust = {n} # The most inner ring
while crust:
    core |= crust
    # The next ring
    crust = set.union(*(set(g.neighbors(i)) for i in crust)) - core

Answer 2

函数nx.single_source_shortest_path_length(G, source=0, cutoff=7)应该提供您需要的信息。但它返回一个由节点键入的dict，以确定与源的距离。所以你必须处理它，让它按距离分组。这样的方法应该有用：

from itertools import groupby
spl = nx.single_source_shortest_path_length(G, source=0, cutoff=7)
rings = [set(nodes) for dist, nodes in groupby(spl, lambda x: spl[x])]