Обход графа — это фундаментальная операция в теории графов, которая широко используется в различных приложениях, таких как сетевой анализ, анализ социальных сетей и алгоритмы поиска пути. Одним из популярных алгоритмов обхода графа является поиск в ширину (BFS). В этой статье мы рассмотрим несколько методов выполнения поиска в ширину на графе, а также приведем примеры кода на Python.

Методы поиска в ширину:

1. Представление списка смежности:
   • Создайте график, используя список смежности.
   • Реализовать структуру данных очереди (FIFO), чтобы отслеживать узлы, которые необходимо посетить.
   • Начните с исходного узла и поставьте его в очередь.
   • Пока очередь не пуста, исключите узел из очереди, пометьте его как посещенный и обработайте его соседей.
   • Поставьте в очередь всех непосещенных соседей и продолжайте процесс, пока очередь не опустеет.

def bfs_adjacency_list(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)
    while queue:
        node = queue.pop(0)
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

2. Представление матрицы смежности:
   • Создайте график, используя матрицу смежности.
   • Реализовать структуру данных очереди, чтобы отслеживать узлы, которые необходимо посетить.
   • Начните с исходного узла и поставьте его в очередь.
   • Пока очередь не пуста, исключите узел из очереди, пометьте его как посещенный и обработайте его соседей.
   • Поставьте в очередь всех непосещенных соседей и продолжайте процесс, пока очередь не опустеет.

def bfs_adjacency_matrix(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)
    num_nodes = len(graph)
    while queue:
        node = queue.pop(0)
        print(node)
        for neighbor in range(num_nodes):
            if graph[node][neighbor] == 1 and neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

3. Использование структуры данных очереди:
   • Создайте график, используя любое представление.
   • Реализуйте структуру данных очереди или используйте встроенную структуру данных, например collections.deque.
   • Начните с исходного узла и поставьте его в очередь.
   • Пока очередь не пуста, исключите узел из очереди, пометьте его как посещенный и обработайте его соседей.
   • Поставьте в очередь всех непосещенных соседей и продолжайте процесс, пока очередь не опустеет.

from collections import deque
def bfs_queue(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

4. Использование рекурсивного подхода:
   • Создайте график, используя любое представление.
   • Реализовать рекурсивную функцию, которая принимает узел для посещения и набор для отслеживания посещенных узлов.
   • Отметить текущий узел как посещенный и рекурсивно обработать его соседей.
   • Повторите процедуру для всех непосещенных соседей.

def bfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            bfs_recursive(graph, neighbor, visited)

Поиск в ширину – это мощный алгоритм обхода графа, который исследует граф в ширину. В этой статье мы рассмотрели четыре различных метода выполнения BFS, включая представление списка смежности, представление матрицы смежности, использование структуры данных очереди и рекурсивный подход. Каждый метод имеет свои преимущества и может подойти в зависимости от решаемой проблемы. Используя эти методы, вы можете эффективно перемещаться по графам и решать широкий спектр проблем, связанных с графами.