Ширина Первый Поиск

Deque является единственной структурой данных Python с быстрой Очереди операций . (Примечание 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}