在BFS遍历中,可能会遇到同一节点被访问两次的情况,通常这是由于节点入队列的时候没有进行去重操作所导致的。为了解决这个问题,我们可以在入队列之前判断该节点是否已经被访问过,如果已经被访问过,则不需要将该节点入队列。下面是一个示例代码:
def bfs(graph, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
node = queue.pop(0)
print(node)
for next_node in graph[node]:
if next_node not in visited:
queue.append(next_node)
visited.add(next_node)
在上面的代码中,我们使用了一个集合visited来记录已经访问过的节点。每次访问一个节点时,将其添加到visited集合中。在遍历节点的邻居节点时,只有那些未访问过的节点才会入队列以供下一次遍历使用。这样就能保证同一节点只会被访问一次了。
上一篇:BFS遍历输出结果错误
下一篇:BFS超时