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

Метод 1: использование списка смежности
Наиболее распространенный способ представления неориентированного графа — использование списка смежности. Вот пример реализации BFS с использованием списка смежности:

from collections import deque
def bfs(graph, start_vertex):
    visited = set()
    queue = deque([start_vertex])
    visited.add(start_vertex)
    while queue:
        vertex = queue.popleft()
        print(vertex)  # Example: Print the visited vertex
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

Метод 2: использование матрицы смежности
Другой подход заключается в использовании матрицы смежности для представления неориентированного графа. Вот пример реализации BFS с использованием матрицы смежности:

from collections import deque
import numpy as np
def bfs(graph, start_vertex):
    num_vertices = graph.shape[0]
    visited = set()
    queue = deque([start_vertex])
    visited.add(start_vertex)
    while queue:
        vertex = queue.popleft()
        print(vertex)  # Example: Print the visited vertex
        for neighbor in range(num_vertices):
            if graph[vertex, neighbor] != 0 and neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

Метод 3: оптимизация BFS с использованием очереди и посещаемого массива
В сценариях, где память имеет значение, мы можем оптимизировать алгоритм BFS, используя очередь и посещаемый массив. Вот пример реализации:

from collections import deque
def bfs(graph, start_vertex):
    num_vertices = len(graph)
    visited = [False] * num_vertices
    queue = deque([start_vertex])
    visited[start_vertex] = True
    while queue:
        vertex = queue.popleft()
        print(vertex)  # Example: Print the visited vertex
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

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