Обход графа в ширину
💻 Информатика · 9 класс
Что такое обход графа в ширину
Граф состоит из вершин и связывающих их рёбер. Обход графа в ширину — это способ посетить все вершины, начиная со стартовой и продвигаясь слоями: сначала все соседи старта, затем соседи соседей и так далее. Такой обход напоминает круги на воде от брошенного камня.
Главный инструмент обхода в ширину — очередь. Это структура данных, в которой элементы добавляются в конец, а извлекаются из начала, по правилу «первым пришёл — первым вышел».
Алгоритм обхода
добавить старт в очередь, отметить его
пока очередь не пуста:
v := взять из начала очереди
для каждого соседа u вершины v:
если u не отмечен:
отметить u, добавить u в очередьКаждая вершина отмечается, чтобы не обрабатывать её дважды. Пока очередь не опустеет, мы берём вершину из начала и добавляем в конец всех её непосещённых соседей.
Разбор примера
Пусть рёбра соединяют вершины так: 1–2, 1–3, 2–4, 3–4. Начнём с вершины 1.
| Шаг | Взяли | Добавили в очередь | Очередь после |
|---|---|---|---|
| 1 | 1 | 2, 3 | 2, 3 |
| 2 | 2 | 4 | 3, 4 |
| 3 | 3 | — | 4 |
| 4 | 4 | — | пусто |
Порядок посещения: 1, 2, 3, 4. Вершина 4 была соседом и для 2, и для 3, но добавилась только один раз благодаря отметке.
Зачем нужен обход в ширину
- Он находит кратчайший путь по числу рёбер от старта до любой вершины.
- Он определяет, до каких вершин вообще можно добраться из старта.
- Он разбивает вершины на слои по удалённости от начальной.
Запомни: отметку «посещено» ставят в момент добавления вершины в очередь, а не когда её достали. Иначе одна и та же вершина может попасть в очередь несколько раз и обход даст лишние повторы.
Сравнение с обходом в глубину
В отличие от обхода в глубину, который уходит как можно дальше по одному пути, обход в ширину равномерно расходится во все стороны. Именно поэтому он первым достигает ближайших вершин и подходит для поиска кратчайшего пути в невзвешенном графе.
Подсчёт расстояний
Обход в ширину легко дополнить подсчётом расстояний от старта. Для этого заводят массив, где для каждой вершины хранят число рёбер до неё. Стартовой вершине ставят расстояние ноль, а каждому новому соседу — на единицу больше, чем у вершины, из которой он был открыт. Так после обхода для любой достижимой вершины известно кратчайшее число шагов от начала.
Этот приём применяют, например, при поиске пути в лабиринте, где клетки считают вершинами, а переходы между соседними клетками — рёбрами. Обход в ширину гарантирует, что найденный путь будет содержать наименьшее число шагов.
Кратко о главном
- Обход в ширину посещает вершины слоями от стартовой, используя очередь.
- Очередь работает по правилу «первым пришёл — первым вышел».
- Вершину отмечают при добавлении в очередь, чтобы не обработать дважды.
- Обход в ширину находит кратчайший путь по числу рёбер.