Просмотр исходного текста страницы Поиск в ширину (BFS)

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

== Основные понятия ==

# '''Граф (Graph)''': Структура данных, состоящая из множества вершин (узлов) и множества ребер, соединяющих эти вершины.
# '''Вершина (Vertex)''': Узел графа.
# '''Ребро (Edge)''': Соединение между двумя вершинами графа.
# '''Очередь (Queue)''': Структура данных, основанная на принципе FIFO (First In, First Out), используемая для хранения информации о вершинах, которые необходимо посетить.
# '''Посещенная вершина (Visited Vertex)''': Вершина, которая уже была обработана алгоритмом BFS.
# '''Непосещенная вершина (Unvisited Vertex)''': Вершина, которая еще не была обработана алгоритмом BFS.
# '''Корень (Root)''': Вершина, с которой начинается обход графа.
# '''Уровень вершины (Level)''': Расстояние от вершины до корня графа.

== Алгоритм BFS ==

1. Создать очередь $Q$ и добавить в нее корень графа.
2. Отметить корень как посещенный.
3. Пока очередь $Q$ не пуста:
   *  Извлечь вершину $v$ из начала очереди $Q$.
   *  Для каждой непосещенной вершины $u$, смежной с $v$:
      *  Отметить вершину $u$ как посещенную.
      *  Добавить вершину $u$ в конец очереди $Q$.

== Реализация BFS ==

=== Пример реализации BFS на Python: ===

```python
from collections import deque

def breadth_first_search(graph, root):
    visited = set()
    queue = deque([root])
    visited.add(root)
    levels = {root: 0}  # Словарь для хранения уровней вершин
    bfs_order = []  # Список для хранения порядка посещения вершин

    while queue:
        vertex = queue.popleft()
        bfs_order.append(vertex)  # Добавляем вершину в порядок посещения

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                levels[neighbor] = levels[vertex] + 1  # Устанавливаем уровень вершины

    return bfs_order, levels

# Пример графа в виде списка смежности
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2, 4],
    4: [3]
}

root = 0
bfs_order, levels = breadth_first_search(graph, root)

print("BFS Order:", bfs_order)
print("Levels:", levels)
```

Вывод:

```
BFS Order: [0, 1, 2, 3, 4]
Levels: {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
```

== Свойства BFS ==

# '''Полнота (Completeness)''': BFS всегда находит кратчайший путь (минимальное количество ребер) от корня до любой достижимой вершины графа.
# '''Временная сложность''': $O(V + E)$, где $V$ — количество вершин, $E$ — количество ребер.
# '''Пространственная сложность''': $O(V)$, так как в очереди может храниться до $V$ вершин.

== Применение BFS ==

BFS используется в широком спектре приложений, включая:

# '''Поиск кратчайшего пути в невзвешенном графе''': BFS гарантированно находит кратчайший путь от заданной вершины до любой другой вершины в невзвешенном графе.
# '''Поиск всех достижимых вершин из заданной вершины''': BFS позволяет найти все вершины, которые достижимы из заданной вершины.
# '''Обход графа по уровням''': BFS обходит граф по уровням, что может быть полезно для решения некоторых задач.
# '''Проверка связности графа''': BFS можно использовать для проверки, является ли граф связным.
# '''Поиск в ширину в играх''': BFS используется для поиска пути в играх, где необходимо найти кратчайший путь между двумя точками.
# '''Сканирование сети''': BFS может использоваться для сканирования сети и обнаружения доступных устройств.

== Примеры использования BFS ==

# '''Поиск кратчайшего пути в лабиринте''':

## Лабиринт можно представить в виде графа, где каждая клетка лабиринта является вершиной, а переходы между соседними клетками — ребрами. BFS можно использовать для поиска кратчайшего пути от начальной клетки до конечной клетки.
# '''Поиск друзей в социальной сети''':

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

== Преимущества и недостатки использования BFS ==

=== Преимущества: ===

# '''Простота реализации''': BFS легко реализовать с использованием очереди.
# '''Гарантированный поиск кратчайшего пути''': BFS гарантированно находит кратчайший путь в невзвешенном графе.
# '''Полный обход графа''': BFS посещает все достижимые вершины графа.

=== Недостатки: ===

# '''Большая пространственная сложность''': BFS требует хранения всех посещенных вершин в очереди, что может привести к большой пространственной сложности для больших графов.
# '''Не подходит для взвешенных графов''': BFS не гарантирует нахождение кратчайшего пути во взвешенных графах. Для поиска кратчайшего пути во взвешенных графах необходимо использовать другие алгоритмы, такие как алгоритм Дейкстры или алгоритм Беллмана-Форда.

Понимание алгоритма BFS и умение его эффективно использовать является важным для разработки качественного и производительного программного обеспечения, работающего с графами.