图节点中的 BFS

Question

Graph

我试图从节点 16 开始在此图上执行 BFS。但是我的代码给出了错误的输出。你能帮帮我吗？谢谢

visited_nodes = set()
queue = [16]
pardaught = dict()
exclu = list()
path = set()
for node in queue:
    path.add(node)
    neighbors = G.neighbors(node)
    visited_nodes.add(node)
    queue.remove(node)
    queue.extend([n for n in neighbors if n not in visited_nodes])

newG = G.subgraph(path)
nx.draw(newG, with_labels=True)

我的输出是： Output

Answer 1

path 应该是 list，而不是 set，因为 set 没有顺序。这应该有效：

visited_nodes = set()
path = []
queue = [16]

while queue:
    node = queue.pop(0)
    visited_nodes.add(node)
    path.append(node)

    for neighbor in G.neighbors(node):
        if neighbor in visited_nodes:
            continue
        queue.append(neighbor)

Answer 2

问题的原因是您在循环遍历 queue 的（开始）时删除了一些东西。当它循环时，它会向前移动，但是因为元素从一开始就被删除了，所以列表会向相反的方向“移动”一个。最终结果是它似乎一次跳了 2 个。这是一个例子：

integer_list = [1,2,3]
next_int = 4
for integer in integer_list:
   print integer
   integer_list.remove(integer)
   integer_list.append(next_int)
   next_int += 1

产生输出

1

3

5

图节点中的 BFS

BFS in the nodes of a graph

python

algorithm

graph

breadth-first-search

networkx