Python中的BFS算法 [英] BFS algorithm in Python

问题描述

graph={ 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }

def bfs(graph, start, path=[]):
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in path:
            path.append(vertex)
            queue.extend(graph[vertex] - path)
    return path

print bfs(graph, 0)

你们好！有人可以帮我这个BFS代码吗？我不明白如何解决此队列行。

Guys! Can someone help me with this bfs code? I can't understand how to solve this queue line.

推荐答案

将队列扩展为路径上尚未出现的所有节点，请使用设置操作：

To extend your queue with all nodes not yet seen on the path, use set operations:

queue.extend(set(graph[vertex]).difference(path))

或使用生成器表达式：

queue.extend(node for node in graph[vertex] if node not in path)

列表不支持减法。

您并不需要 来过滤节点，但是，您的代码可以使用简单：

You don't really need to filter the nodes, however, your code would work with a simple:

queue.extend(graph[vertex])

，因为如果顶点不在路径中：测试还可以防止重新访问节点。

as the if vertex not in path: test also guards against re-visiting nodes.

您不应使用列表作为默认参数，请参见最少惊讶和可变默认参数；您根本不需要默认参数：

You should not use a list as default argument, see "Least Astonishment" and the Mutable Default Argument; you don't need a default argument here at all:

def bfs(graph, start):
    path = []

演示：

>>> graph={ 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }
>>> def bfs(graph, start):
...     path = []
...     queue = [start]
...     while queue:
...         vertex = queue.pop(0)
...         if vertex not in path:
...             path.append(vertex)
...             queue.extend(graph[vertex])
...     return path
... 
>>> print bfs(graph, 0)
[0, 1, 3, 4, 2, 6, 5]

这篇关于Python中的BFS算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！