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

要使用路径上尚未看到的所有节点扩展队列，请使用集合操作：

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]

Answer 2

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 3

Bug是没有列表差异方法。您可以将其转换为集合并使用集合差异方法，也可以使用列表理解作为

queue.extend(图[顶点] - 路径)

可以替换为

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

Answer 4

 #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 5

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