Алгоритмы. Представление графов и обход в ширину (BFS)

Новая неделя и новый раздел в изучении алгоритмов. Мы плавно переходим к теме алгоритмов на графах и сегодня поговорим о BFS.

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

    A --- B
    |     |
    C --- D

Здесь буквы A, B, C и D обозначают вершины, а линии между ними — рёбра, то есть связи.

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

# Граф из примера выше
graph = {
    "A": ["B", "C"],      # из A можно попасть в B и C
    "B": ["A", "D"],      # из B можно попасть в A и D
    "C": ["A", "D"],      # из C можно попасть в A и D
    "D": ["B", "C"]       # из D можно попасть в B и C
}

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

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

Реализация алгоритма на языке Python выглядит следующим образом:

from collections import deque

def bfs(graph, start_node):
    # 1. Создаём множество для отслеживания посещённых вершин
    visited = set()
    
    # 2. Создаём очередь и добавляем стартовую вершину
    queue = deque([start_node])
    
    # 3. Помечаем стартовую вершину как посещённую
    visited.add(start_node)
    
    # 4. Список для сохранения порядка обхода
    result = []
    
    # 5. Пока в очереди есть вершины
    while queue:
        # Достаём первую вершину из очереди
        node = queue.popleft()
        result.append(node)
        
        # Смотрим на всех соседей этой вершины
        for neighbor in graph.get(node, []):
            # Если соседа ещё не посещали
            if neighbor not in visited:
                # Помечаем как посещённого
                visited.add(neighbor)
                # Добавляем в очередь для будущего посещения
                queue.append(neighbor)
    
    return result

Рассмотрим работу алгоритма на конкретном графе:

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

Визуально этот граф можно представить так:

        A
       / \
      B   C
     /|   |
    D E   F
       \ /

Пошаговое выполнение BFS, стартующего от вершины A, будет происходить в таком порядке: