Крипто Devs | Gnezdo Hub on Telegram: “Шаг 0: Очередь: [A] Посещённые: {A} Результат: […”

Шаг 0:
Очередь: [A]
Посещённые: {A}
Результат: []

Шаг 1: Обрабатываем A
Очередь: [B, C]
Посещённые: {A, B, C}
Результат: [A]

Шаг 2: Обрабатываем B
Соседи B: A (уже посещён), D, E
Очередь: [C, D, E]
Посещённые: {A, B, C, D, E}
Результат: [A, B]

Шаг 3: Обрабатываем C
Соседи C: A (уже посещён), F
Очередь: [D, E, F]
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C]

Шаг 4: Обрабатываем D
Соседи D: B (уже посещён)
Очередь: [E, F]
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C, D]

Шаг 5: Обрабатываем E
Соседи E: B (уже посещён), F (уже посещён)
Очередь: [F]
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C, D, E]

Шаг 6: Обрабатываем F
Соседи F: C (уже посещён), E (уже посещён)
Очередь: []
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C, D, E, F]

Именно использование очереди, которая следует принципу FIFO, и обеспечивает этот порядок обработки вершин слой за слоем.

Ключевым практическим применением BFS является поиск кратчайшего пути в невзвешенном графе. Так как алгоритм исследует вершины по уровням, первый найденный путь до целевой вершины гарантированно будет иметь минимальную длину в терминах количества рёбер. Для этого можно слегка модифицировать базовый алгоритм, храня в очереди не просто вершины, а целые пути:

def bfs_shortest_path(graph, start, end):
    visited = set()
    queue = deque([[start]])  # Храним путь, а не только вершину
    visited.add(start)
    
    while queue:
        path = queue.popleft()
        node = path[-1]  # Последняя вершина в текущем пути
        
        if node == end:
            return path  # Нашли кратчайший путь!
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                new_path = path + [neighbor]
                queue.append(new_path)
    
    return None  # Пути нет

Например, для графа ниже:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "E"],
    "D": ["B", "E"],
    "E": ["C", "D", "F"],
    "F": ["E"]
}

print(bfs_shortest_path(graph, "A", "F"))
# Результат: ['A', 'C', 'E', 'F']

Алгоритм вернёт один из кратчайших путей.

Другим полезным применением BFS является определение расстояния от начальной вершины до всех остальных, то есть их уровня. Для этого в очередь вместе с вершиной помещается и информация о её текущем уровне:

def bfs_levels(graph, start):
    visited = set()
    queue = deque([(start, 0)])  # (вершина, уровень)
    visited.add(start)
    levels = {}
    
    while queue:
        node, level = queue.popleft()
        levels[node] = level
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, level + 1))
    
    return levels

Это может быть полезно, например, для анализа социальных сетей, где вершины — это люди, а рёбра — дружеские связи. Запустив BFS от своего профиля, можно найти всех своих друзей и друзей друзей.

Часто возникает вопрос о различии между BFS и обходом в глубину. Основное отличие заключается в стратегии исследования. BFS исследует граф послойно, используя очередь, и потому находит кратчайший путь. DFS же, используя стек или рекурсию, идёт по одному пути до конца, прежде чем вернуться и исследовать другие ветви. Визуально это можно представить так: для дерева с корнем A, детьми B и C, и внуками D, E у B и F у C, BFS даст порядок A, B, C, D, E, F, а DFS может дать порядок A, B, D, E, C, F.

Сложность алгоритма BFS составляет O(V + E), где V — число вершин, а E — число рёбер, так как каждая вершина и каждое ребро обрабатываются один раз. Пространственная сложность оценивается как O(V), поскольку в худшем случае необходимо хранить все вершины в очереди и множестве посещённых.

📟 Прилетело из @solidityset