Ученик выучил несколько обходов графа, но на новой задаче сомневается, какой использовать. Помогает вопрос о требуемом результате. Нужно найти все достижимые вершины, восстановить кратчайший путь или вычислить расстояния с учетом разных весов? Внешне похожие циклы решают разные задачи, поэтому выбор начинается с модели, а не с знакомого названия алгоритма.
DFS подходит для поиска компонент связности и проверки достижимости. Из текущей вершины мы продолжаем путь к непосещенному соседу, а после завершения ветви возвращаемся назад. Реализация использует рекурсию или явный стек. Порядок посещения зависит от порядка соседей.
В неориентированном графе, чтобы посчитать компоненты, запускают обход из каждой еще не посещенной вершины. Один запуск отмечает всю соответствующую компоненту. Кратчайшие расстояния в произвольном невзвешенном графе такой порядок посещения не обеспечивает: первая найденная дорога может оказаться длиннее другой.
BFS посещает вершины по слоям расстояния от старта. Сначала идут вершины на расстоянии один, затем два и дальше. Для графа с одинаковой стоимостью каждого ребра это дает кратчайшие пути по числу ребер. Очередь обеспечивает нужный порядок обработки.
На прямоугольной сетке без взвешенных переходов BFS помогает найти минимальное число шагов между клетками. При добавлении клетки в очередь ее обычно сразу отмечают посещенной, чтобы не добавлять повторно из разных соседей. Для восстановления пути сохраняют предка, а после достижения цели идут по предкам обратно к старту.
Если ребра имеют стоимость ноль или один, обычные слои по числу ребер уже не совпадают со стоимостью пути. BFS 0-1 использует двустороннюю очередь: при улучшении расстояния по нулевому ребру вершину добавляют в начало, по единичному — в конец. Проверка улучшения расстояния заменяет простое правило первого посещения.
Здесь нельзя бездумно перенести логику обычного BFS. Вершина может получить более короткий путь после первого обнаружения. Если встречаются другие неотрицательные веса, нужен иной алгоритм, например Дейкстры. Выбор зависит от ограничений на веса, а не от того, насколько удобно написать очередь.
До программирования определите, ориентирован ли граф, существуют ли изолированные вершины и как задаются ребра. При хранении списками смежности DFS и обычный BFS работают за O(V + E). Для сетки оценка переводится в число клеток и разрешенных переходов между ними.
Для подготовки к олимпиадам по информатике полезно решить один сюжет в нескольких вариантах: все переходы равны, некоторые бесплатны, затем веса произвольны. Так становится видно, какая часть алгоритма отвечает за правильный порядок обработки.
Для рекурсивного DFS учитывайте глубину: длинная цепочка может создать слишком много вложенных вызовов. В таком случае явный стек сохраняет идею обхода, но меняет организацию выполнения программы.
Проверьте единственную вершину, отсутствие пути, несколько одинаково коротких путей и цикл. Для BFS 0-1 добавьте пример, где более длинный по числу ребер маршрут дешевле короткого. После успешного решения объясните, почему выбранная структура обработки вершин соответствует именно требуемой стоимости пути.