Python的广度优先遍历,Python

Question

我想出了一棵树的深度优先遍历.

def _dfs(tree, res):
    if tree:
        res += [tree.key]
        _dfs(tree.left, res)
        _dfs(tree.right, res)
    return res

我似乎无法找到广度优先搜索的解决方案.是否必须使用队列或堆栈？

谢谢!!

Answer 1

你可以去deques.这是来自Magnus Lie Hetland(使用FIFO队列)的bfs的经典实现.

from collections import deque

def bfs(G, s):
    P, Q = {s: None}, deque([s]) 
    while Q:
        u = Q.popleft() 
        for v in G[u]:
            if v in P: continue 
            P[v] = u 
            Q.append(v)
    return P