Python中的BFS算法

Question

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）的代码？我搞不懂怎么处理这个队列的问题。

Answer 1

def breadthFirstSearch(problem: SearchProblem):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"
    start=problem.getStartState()
    fringe=util.Queue()
    visited=set()
    fringe.push((start,[]))
    while not fringe.isEmpty():
        current_state,action=fringe.pop()
        if problem.isGoalState(current_state):
            return action
        visited.add(current_state)
        successor=problem.getSuccessors(current_state)
        for next_state,actions,_ in successor:
                   if next_state not in visited:
                    next_actions = action+[actions]
                    fringe.push((next_state, next_actions))
    return []
    BFS for maze search game

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 2

在编程中，有时候我们会遇到一些问题，可能会让我们感到困惑。比如，有人可能会问，为什么代码在某种情况下会出错，而在其他情况下却能正常运行。这种情况通常和代码的逻辑、数据的处理方式或者环境的设置有关。

当我们写代码时，实际上是在给计算机下指令，让它按照我们的想法去做事情。如果指令不够清晰，或者数据不符合预期，计算机就会出现错误。

为了避免这些问题，我们可以采取一些措施，比如仔细检查代码、使用调试工具，或者在代码中加入一些打印信息，帮助我们了解程序的运行情况。

总之，编程就像是在和计算机沟通，确保我们说的每一句话都能被它理解，这样才能顺利完成我们的任务。

 #USE BELOW CODE FOR SIMPLE UNDERSTANDING

    

  
graph = {
    'A' : ['B' , 'C','D'],
    'B' : ['E'],
    'C' : ['F'],
    'D' : ['G'],
    'E' : [],
    'F' : ['Z'],
    'G' : [],
    'Z' : [],
}


visited = [] #Store visted nodes
queue = [] #BFS uses queue structure so this varible will work like QUEUE ( LIFO)
final_result = [] 

def bfs(visited,graph,node):
    visited.append(node)
    queue.append(node)
    
    while queue:
        s = queue.pop(0)
        print(s,end=" ")
        #final_result.append(s)
        
        for neighbour in graph[s]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)
    

    bfs(visited,graph,'A')
    print(final_result) 

Answer 3

这个问题是说没有直接的方法来找出两个列表之间的不同之处。你可以把列表转换成集合，然后用集合的方法来找不同，或者你可以用列表推导式来实现。

比如，原来的写法是：

queue.extend(graph[vertex] - path)

这可以换成：

queue += [i for i in graph[vertex] if i not in path]。

Answer 4

queue.extend(graph[vertex] - path)

这一行代码出现了 TypeError: unsupported operand type(s) for -: 'list' and 'list' 的错误，因为你不能直接用减法来操作两个列表。你可以把它们转换成其他支持差值的集合。例如：

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(set(graph[vertex]) - set(path))
    return path

print bfs(graph, 0)

结果：

[0, 1, 3, 4, 2, 6, 5]

顺便提一下，修改参数列表可能是个好主意，这样你就不会有一个可变的列表作为默认值了：

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

Answer 5

要把你的队列扩展到所有在路径上还没见过的节点，可以使用集合操作：

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

或者你可以用生成器表达式：

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

列表不支持减法操作。

不过，其实你并不需要过滤这些节点，你的代码用一个简单的方式也能工作：

queue.extend(graph[vertex])

因为 if vertex not in path: 这个检查也能防止重新访问节点。

你不应该把列表作为默认参数，具体可以参考“最少惊讶原则”和可变默认参数; 在这里你根本不需要默认参数：

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]