廣度優先搜尋

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}