Ранней работой по поиску в ширину стала докторская диссертация 1945 года немецкого инженера Конрада Цузе: её отклонили и не публиковали до 1972 года. В 1959 и 1961 годах два независимых исследователя описали схожие обходы графов. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов разбирают метод, который проходит граф из 14 вершин за пять слоёв.
Рис. 1. Волна расходится от старта кольцами: 13 шагов дерева и 5 рёбер внутри слоёв
Эдвард Мур в 1959 году опубликовал алгоритм прохождения лабиринта, задавший порядок работы поиска в ширину. Через два года Чан Ли предложил схожий метод разводки проводов на печатных платах: волна расходится от первого контакта, пока не дотянется до второго, а обратный ход собирает готовую дорожку. Две далёкие задачи оказались одним и тем же обходом графа, найденным независимо.
Алгоритм относится к волновым. Он исходит из начальной вершины и слой за слоем изучает соседей, придерживаясь принципа first in – first out: первым зашёл – первым вышел. Пошаговый обход вех позволяет находить кратчайшие пути в невзвешенных графах.
В отличие от собрата, работающего с глубиной, поиск в ширину создаёт виртуальную очередь. Это повышает прозрачность, но «съедает» тем больше памяти, чем шире граф. Зато ширина обнаруживает кратчайшие пути, чем не может похвастаться глубинный поиск.
Поиск в ширину нетрудно реализовать на любом языке программирования. Главное – зафиксировать правила посещения через последовательность. Задачу разбивают на слои и решают динамическим программированием: так проще отследить, откуда в каждую вершину пришли и на каком шаге она попала в очередь.
Разберём метод на примере. Дан граф из 14 вершин: некоторые точки связаны рёбрами, ориентира движения нет, веса неважны (рисунок 2). Работу начинаем с вершины 1 и заводим очередь – список тех, чьи окрестности ещё предстоит осмотреть. Пока очередь не опустеет, алгоритм не остановится и не пропустит ни одной точки.
Рис. 2. Начальный граф, точка старта – вершина 1
Из вершины 1 ведут три направления: 1–2, 1–3 и 1–5 (рисунок 3). Все три соседа попадают в очередь одновременно и образуют второй слой. Порядок внутри слоя задаёт очерёдность следующего шага.
Рис. 3. Пути исследования соседей из вершины 1
Помечаем вершины 2, 3 и 5 как изученные и двигаемся дальше (рисунок 4). Под взор попадают точки 11, 9, 4 и 12. Для вехи 4 путь выбирается по правилу очереди: тройка встала в неё раньше пятёрки, поэтому ребро 5–4 остаётся невостребованным. Так третий слой набирается из четырёх новых для алгоритма точек.
Рис. 4. Разметка графа на уровень 3
Вершина 9 уже посещена, поэтому путь 11–9 не создаётся. Направляемся к соседям четвёртого уровня (рисунок 5). После обследования новых точек появляются ещё три невостребованных направления: 14–13, 10–13 и 10–8. Для завершения графа остаётся посетить веху 7.
Рис. 5. Разметка графа на уровень 4
Итоговый граф перед вами (рисунок 6). Поиск в ширину оставил 5 рёбер невостребованными: их концы оказались в одном слое или в уже пройденном.
Рис. 6. Изученный в ширину граф
Для программной реализации нужна виртуальная очередь, куда вносятся посещённые вершины. Для нашего случая из точки 1 последовательность будет {2, 3, 5}. На следующем шаге алгоритм сначала посмотрит соседей двойки (11), затем тройки (9 и 4), а закончит пятёркой (12).
Временная сложность метода совпадает с поиском в глубину:
T = O(V + E),
где T – время работы, V – число вершин, E – количество рёбер.
Требования к памяти зависят от числа вершин и глубины:
Q = O(V) – для общего случая,
Q = O(bd) – для глубокого графа,
где Q – объём памяти, V – число вершин, b – коэффициент ветвления, d – глубина дерева.
Алгоритм подойдёт, если нужен кратчайший путь или проверка, есть ли путь до вершины. Метод считает минимальное число ходов в головоломках, прокладывает маршруты в играх, индексирует интернет-ресурсы и анализирует социальные сети.
Какой алгоритм выбрать?
Ширина предпочтительнее, когда нужен кратчайший путь в невзвешенном графе и есть основания считать, что решение близко к корню. Глубина берёт верх на перечислении всех маршрутов, комбинациях и перестановках, а также на циклах и топологической сортировке.
В чём преимущество поиска в ширину?
Алгоритм выдаёт кратчайшие пути в невзвешенных графах и не даёт погрязнуть в циклах. У метода понятная последовательность шагов, что делает поиск предсказуемым. Программный код немного сложнее, чем у поиска в глубину.
Сколько проходов делает алгоритм?
Каждую вершину алгоритм ставит в очередь один раз, а каждое ребро проверяет дважды – с обоих концов. Число заходов зависит только от вершин и связей между ними.
Где поиск в ширину проигрывает?
На больших графах с обильным ветвлением алгоритм упрётся в нехватку памяти: очередь хранит целый слой сразу. Во взвешенных задачах и на крупных пространствах быстрее сработают Дейкстра или A* – «А со звёздочкой».
Очередь или стек?
Разница в одной структуре данных. Поиск в ширину берёт вершины из головы очереди, поэтому расходится слоями и первым же находит кратчайший путь. Поиск в глубину снимает их с вершины стека и уходит по одной ветке до упора. Замените очередь стеком – и тот же код без иных правок превратится в обход в глубину.
Как восстановить сам маршрут?
Достаточно запоминать предшественника: при первом попадании в вершину записываем, откуда пришли. В конце путь собирается обратным ходом от финиша к старту. Массив предшественников стоит одну ячейку на вершину и не меняет ни сложности алгоритма, ни порядка обхода.
Рис. 7. Пять шагов поиска в ширину и цифры разобранного графа
Что запомнить?
Поиск в ширину идёт по уровням и сортирует соседей через виртуальную очередь. Метод изучает вершины по правилу «первым зашёл – первым вышел». Он отлично находит быстрые маршруты, но платит за это высокими требованиями к памяти.
Ширина и глубина – две стороны одного обхода: меняется только структура, в которой ждут своей очереди вершины. Выбирайте ширину, когда важен кратчайший маршрут, и глубину, когда важно перебрать все варианты до единого.