Зонтичная тема: что общего у обоих обходов, как увидеть в задаче, где он не назван, и по каким двум вопросам выбирается обход. Сами обходы разобраны отдельно.
Ключевые тезисы
- Оба обхода линейны по числу вершин и рёбер: O(V + E), и отличаются одной строкой — откуда берётся следующая вершина.
- Половина «графовых» задач приходит без слова «»: лабиринт, зависимости, превращения строк, состояния игры.
- Составное состояние — это вершина целиком: неполный ключ посещённых даёт не медленный, а неверный ответ.
Какую задачу решает
Обход — не один алгоритм, а схема, у которой два наполнения. и поиск в глубину отличаются одной строчкой (откуда берём следующую вершину) и решают разные задачи: первый — по числу шагов, второй — связность, циклы, порядок и полный перебор вариантов.
Эта страница — про семейство: что у обходов общего, как разглядеть в задаче, где слово «граф» не встречается, и по каким вопросам выбирается нужный обход. Сами обходы разобраны каждый на своей странице.
Внутри темы
2 приёма разобраны на отдельных страницах — по одной и той же схеме. Эта страница про то, что у них общее и как выбрать нужный.
Breadth-First Searchактуально
Поиск в ширинуОбход слоями: сначала всё, до чего один шаг, потом — два. Первое посещение вершины оказывается кратчайшим путём, если все переходы равноценны.
Depth-First Searchактуально
Поиск в глубинуИдти вглубь до упора и возвращаться. Порядок завершения вершин даёт топологическую сортировку, три цвета — обнаружение циклов, откат состояния — перебор с возвратом.
Подробный разбор
и поиск в глубину отличаются одной строчкой: откуда брать следующую вершину. Всё остальное у них общее — множество посещённых, правило «каждую вершину обрабатываем один раз» и линейная сложность : каждая вершина извлекается однажды, каждое ребро просматривается однажды (в неориентированном — дважды).
| В ширину | В глубину | |
|---|---|---|
| Откуда берём следующую вершину | из (FIFO) | из стека или (LIFO) |
| Порядок обхода | по слоям от старта | вглубь одной ветки до упора |
| по числу рёбер | да | нет |
| Память | — целый слой | — глубина обхода |
| Что даёт даром | расстояния в шагах | времена входа и выхода, порядок завершения |
Оба обхода требуют множества посещённых — не для скорости, а для завершимости: без него цикл в означает бесконечную работу.
Большая часть задач на обходы выглядит как задачи про карты, лабиринты, зависимости и превращения. Алгоритм в них не меняется; меняется только ответ на два вопроса: что считать вершиной и что — ребром.
| Формулировка | Вершина | Ребро |
|---|---|---|
| Лабиринт, острова, заливка цветом | клетка сетки | переход к соседней проходимой клетке |
| «За сколько ходов из A получить B» | состояние (строка, число, позиция) | разрешённое преобразование |
| Зависимости задач или пакетов | задача | «должна идти раньше» |
| Друзья, подписки, транзакции | участник | связь между участниками |
| Игра с фиксированными ходами | позиция на доске | ход |
Если состояние составное — позиция плюс собранные ключи, номер шага, остаток топлива, — то вершиной является весь кортеж, и в множество посещённых кладётся тоже он целиком. Пропущенная часть состояния здесь даёт не медленный, а неверный ответ.
- Нужен кратчайший путь по числу шагов? Да — обход в ширину. Стоимость переходов разная — кратчайшие пути с Дейкстрой.
- Нужно обойти всё: связность, циклы, порядок, все варианты? Обход в глубину.
- Граф огромный, а цель одна и известна? Двунаправленный или A* с эвристикой.
- Граф — дерево? Любой обход; множество посещённых не нужно, достаточно не возвращаться в родителя.
Частая ошибка выбора — взять там, где нужен : он найдёт какой-то путь, и на большинстве тестов тот даже окажется коротким.
Чем заменяют
Видеолекции
Записи университетских курсов, где эта тема звучит. Тайм-кодов у них нет, поэтому открываются они с начала.
Связанные темы
Алгоритмы на графах
Breadth-First Search85%
Поиск в ширину · Алгоритмы и структуры данныхОбход слоями: сначала всё, до чего один шаг, потом — два. Первое посещение вершины оказывается кратчайшим путём, если все переходы равноценны.
Depth-First Search85%
Поиск в глубину · Алгоритмы и структуры данныхИдти вглубь до упора и возвращаться. Порядок завершения вершин даёт топологическую сортировку, три цвета — обнаружение циклов, откат состояния — перебор с возвратом.
Shortest Paths85%
Кратчайшие пути · Алгоритмы и структуры данныхДейкстра для неотрицательных весов, Беллман — Форд для отрицательных, A* — когда есть оценка расстояния до цели.
Graph Basics85%
Основы графов · Графы и сетиВершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.
Centrality85%
Центральности · Графы и сетиМеры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.
PageRank85%
PageRank · Графы и сетиСтационарное распределение случайного блуждания по графу с телепортацией. Классический алгоритм ранжирования, который до сих пор используется как признак.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
Поиск в ширину
Обход слоями: первое посещение — по числу рёбер.
Отдельная тема: Breadth-First Search — Поиск в ширинуПоиск в глубину
Вглубь до упора: компоненты, циклы, топологический порядок, перебор с возвратом.
Отдельная тема: Depth-First Search — Поиск в глубинуМоделирование графом
Что считать вершиной и ребром в задаче про лабиринт, зависимости или превращения.
Разбор ниже: Увидеть граф в задачеМножество посещённых
Нужно не для скорости, а для завершимости: цикл иначе означает бесконечный обход.
Разбор ниже: Что общего у обоих обходовСоставное состояние
Вершина — весь кортеж: позиция, ключи, остаток ресурса.
Разбор ниже: Увидеть граф в задачеСпрашивают на собеседовании: 2ГИС — Геопоиск и навигация.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.