广度优先搜索

Deque 是唯一具有快速队列操作的 Python 数据结构。 （注意 queue.Queue 通常不合适，因为它用于线程之间的通信。）Queue 的基本用例是广度优先搜索 。

from collections import deque

def bfs(graph, root):
    distances = {}
    distances[root] = 0
    q = deque([root])
    while q:
        # The oldest seen (but not yet visited) node will be the left most one.
        current = q.popleft()
        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                # When we see a new node, we add it to the right side of the queue.
                q.append(neighbor)
    return distances

假设我们有一个简单的有向图：

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

我们现在可以找到一些起始位置的距离：

>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}