breadth.md

Поиск в ширину

| Главная | Графы |

Поиск в ширину (англ. breadth-first search, BFS) — один из методов обхода графа. Алгоритм поиска в ширину систематически обходит все ребра графа для «открытия» всех вершин, достижимых из вершины v, вычисляя при этом расстояние (минимальное количество рёбер) от v до каждой достижимой из вершины u. Алгоритм работает как для ориентированных, так и для неориентированных графов. Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, т.е. перед тем как приступить к поиску вершин на расстоянии k+1, выполняется обход вершин на расстоянии k.

Реализация

• Без использования рекурсии, используя список смежности

Время	Память
O(V + E)	O(V)

def bfs(graph, start):
    visited = dict().fromkeys(graph, False) # False - белая вершина, True - черная вершина
    queue = [start]
    while queue:
        v = queue.pop(0)
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                queue.append(u)
    return visited

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


print(bfs(g, 1)) #  {0: True, 1: True, 2: True, 3: True, 4: True, 5: True, 6: True, 7: True}