Поиск в ширину и глубину

Зачем нужны поиск в ширину и поиск в глубину

В задачах по графам легко потеряться: вершины обозначены буквами, рёбра перепутаны, а вопрос звучит коротко — «найдите порядок обхода». Разберись в двух алгоритмах поиска, и ты научишься уверенно проходить карты, проверять связность и находить кратчайший путь в невзвешенном графе. Главное — понять не только правила, но и логику выбора следующей вершины.

Граф состоит из вершин и рёбер между ними. Например, вершины могут быть городами, а рёбра — дорогами. Обход графа начинается с выбранной стартовой вершины. Посещённые вершины отмечают, чтобы не ходить по кругу и не повторять одну и ту же работу.

Поиск в ширину, или BFS, сначала обрабатывает ближайших соседей, затем вершины на расстоянии два, потом на расстоянии три. Поиск в глубину, или DFS, идёт по одному направлению как можно дальше, а затем возвращается назад. Для закрепления базовых шагов можно открыть бесплатную практику в личном кабинете и решать задачи сразу после теории.

Поиск в ширину: идея и алгоритм

В BFS используется очередь. Очередь работает по правилу FIFO: первым добавлен — первым обработан. Сначала помести стартовую вершину в очередь и отметь её посещённой. Затем повторяй три действия: достань вершину из начала очереди, рассмотрись её соседей, добавь в очередь тех соседей, которых ещё не было.

Почему вершины обходятся слоями? Если старт находится на расстоянии 0, его соседи находятся на расстоянии 1. Когда обработаны все вершины расстояния 1, в очередь уже попали вершины расстояния 2. Поэтому BFS особенно полезен для поиска кратчайшего пути в графе без весов: число рёбер до вершины будет минимальным.

Если граф задан списками смежности, время работы BFS обычно равно O(V + E), где V — число вершин, а E — число рёбер. Важно не забыть массив visited: без него цикл может зациклить алгоритм.

Поиск в глубину: стек и возврат

DFS строит обход иначе. Из текущей вершины выбирается непосещённый сосед, затем из него — следующий. Так продолжается, пока идти дальше нельзя. После этого алгоритм возвращается к предыдущей вершине и пробует другой путь. Такой возврат называют backtracking, или откатом.

Реализовать DFS можно рекурсией: функция отмечает вершину, перебирает её соседей и вызывает себя для каждого непосещённого соседа. Другой вариант — явный стек. Стек работает по правилу LIFO: последним добавлен — первым извлечён. В задачах на порядок обхода это может менять последовательность, поэтому соседей нужно рассматривать в указанном порядке.

DFS удобен для проверки связности, поиска компонент, обнаружения циклов и перебора вариантов. В отличие от BFS, он не гарантирует кратчайший путь в невзвешенном графе. Если граф имеет несколько компонент, один запуск из стартовой вершины посетит только её компоненту.

Время работы DFS также обычно O(V + E). Глубина рекурсии может стать большой, поэтому для длинных графов безопаснее использовать собственный стек.

Разобранный пример: сравниваем обходы

Рассмотрим неориентированный граф. Будем начинать из вершины A, а соседей просматривать по алфавиту. Для BFS записываем очередь, для DFS — текущий путь и возвраты.

Рёбра: A—B, A—C, B—D, B—E, C—F, E—F
Старт: A
BFS: A → B, C → D, E, F
Порядок BFS: A, B, C, D, E, F
DFS: A → B → D → возврат → E → F → возврат → C
Порядок DFS: A, B, D, E, F, C

Разберём BFS полностью. В начале очередь содержит A, а посещена только A. Достаём A и добавляем B, C. Теперь обрабатываем B: сосед A уже посещён, поэтому добавляем D и E. Очередь выглядит так: C, D, E. Затем обрабатываем C: A уже была посещена, F добавляется в конец. Очередь: D, E, F. После обработки D новых вершин нет, затем обрабатываются E и F. Получаем порядок A, B, C, D, E, F.

В DFS после A выбираем B, затем D. У D нет нового соседа, поэтому возвращаемся к B и выбираем E. Из E попадаем в F, а уже из F видим C. Оба алгоритма посетили все вершины, но порядок и свойства обхода различаются. Для тренировки похожих графов используй личный кабинет с бесплатными заданиями.

Ошибки и выбор алгоритма

Первая ошибка — отмечать вершину посещённой слишком поздно. Делай это в момент добавления в очередь или стек. Иначе одна вершина может попасть туда несколько раз. Вторая ошибка — забывать про направление рёбер. В ориентированном графе из A → B нельзя автоматически перейти из B в A.

Третья ошибка — считать любой найденный DFS-путь кратчайшим. DFS может сначала уйти в длинную ветку, хотя рядом существует короткий маршрут. Для невзвешенного кратчайшего пути выбирай BFS. Если рёбра имеют веса, обычный BFS уже не подходит: обычно нужен алгоритм Дейкстры.

Признак	BFS	DFS
Структура	Очередь	Стек или рекурсия
Обход	Слоями	Вглубь с возвратом
Кратчайший путь без весов	Да	Нет
Типичные задачи	Расстояния, уровни	Компоненты, циклы, перебор

Что запомнить

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

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