def bfs(graph, root):
    visited, queue = [], [root]
    while queue:
        vertex = queue.pop(0)
        for w in graph[vertex]:
            if w not in visited:
                visited.append(w)
                queue.append(w)

graph = {0: [1, 2], 1: [2], 2: []}
bfs(graph, 0)


这看起来像Python 3中BFS的正确实现吗？

#1 楼



set s对列表执行包含检查（w in visited）\ $ O（1）\ $而不是\ $ O（n）\ $。

collections.deque比列表更好用于在前面弹出元素（popleft）。
应将示例代码放在if __name__ == '__main__'子句下。更加明确。

import collections


def breadth_first_search(graph, root): 
    visited, queue = set(), collections.deque([root])
    while queue: 
        vertex = queue.popleft()
        for neighbour in graph[vertex]: 
            if neighbour not in visited: 
                visited.add(neighbour) 
                queue.append(neighbour) 


if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: []} 
    breadth_first_search(graph, 0)



鉴于越来越多的注释表明该代码不返回任何内容，我想补充一点，该代码不处理节点：它仅遍历图形，您可能想添加自己的自定义逻辑来处理每个节点。由于您的里程可能会有所不同（建立遍历列表，找到第一个满足条件的节点，等等），因此没有“一个代码适合所有人”的方法，但是一个有用的第一近似方法是对每个节点按原样进行w遍历：

import collections


def breadth_first_search(graph, root): 
    visited, queue = set(), collections.deque([root])
    while queue: 
        vertex = queue.popleft()
        yield vertex
        visited.add(vertex)
        queue.extend(n for n in graph[vertex] if n not in visited)


if __name__ == '__main__':
    graph = {1: [2, 4, 5], 2: [3, 6, 7], 3: [], 4: [], 5: [], 6: [], 7: []}
    list(breadth_first_search(graph, 1))  # [1, 2, 4, 5, 3, 6, 7]


请注意，此替代迭代还解决了此答案中提到的错误

评论

\ $ \ begingroup \ $
但是代码是从右边弹出元素吗？
\ $ \ endgroup \ $
–克里斯托弗·奥尔森（Christofer Ohlsson）
18年8月2日在14:44
\ $ \ begingroup \ $
@ChristoferOhlsson哪个代码？ OP使用从左侧弹出的list.pop（0），而我使用也从左侧弹出的deque.popleft（）。
\ $ \ endgroup \ $
–301_Moved_Permanently
18年8月2日在14:48
\ $ \ begingroup \ $
对不起，我一定是瞎子。由于某种原因，我没有意识到OP使用0作为参数。
\ $ \ endgroup \ $
–克里斯托弗·奥尔森（Christofer Ohlsson）
18年8月2日在14:51
\ $ \ begingroup \ $
您忘记了“回访”
\ $ \ endgroup \ $
– Andreas K.
18-10-2在8:39
\ $ \ begingroup \ $
我仍然对此感到震惊，但是它没有返回任何正确的信息？
\ $ \ endgroup \ $
–斯科特·斯基尔斯（Scott Skiles）
19年5月17日在2:07

#2 楼

我同意Mathias Ettinger对set和deque的使用，但有两个更改：


将集合命名为seen而不是visited，因为您的算法是在访问之前添加的。

在进入while循环之前将根添加到seen。否则，可能会重新访问根（例如，下面的测试案例，其中1指向0）。

import collections

def bfs(graph, root):
    seen, queue = set([root]), collections.deque([root])
    while queue:
        vertex = queue.popleft()
        visit(vertex)
        for node in graph[vertex]:
            if node not in seen:
                seen.add(node)
                queue.append(node)

def visit(n):
    print(n)

if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2, 0], 2: []} 
    bfs(graph, 0)


输出：

0
1
2




#3 楼

这个想法是在移动到下一个顶点之前完全探索顶点。对于下面的邻接矩阵：

test_graph = {
    1: [2, 4, 5],
    2: [3, 6, 7],
    3: [],
    4: [],
    5: [],
    6: [],
    7: []
}


输出应为1, 2, 4, 5, 7, 6, 3或1, 5, 4, 2, 3, 6, 7等。其想法是，在移至下一个顶点之前，应完全探究当前顶点。顶点。此外，连接的顶点可以按任何顺序出现。

下面的代码提供了正确的顺序

import collections

def bfs(graph, start_vertex):
    visited = set()
    traversal = []
    queue = collections.deque([start_vertex])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            traversal.append(vertex)
            queue.extend(reversed(graph[vertex]))   # add vertex in the same order as visited
    return traversal