BFS/DFS на Python: как решать + 5 задач с проверкой

BFS/DFS — это два базовых способа «обойти» граф: пройти по всем достижимым вершинам из стартовой, отмечая посещённые. В задачах это встречается как лабиринты на клетчатом поле, карты с «островками», сети дорог/трамваев, связи между кабинетами, эвакуационные пути и вообще любые объекты вида «точки и переходы между ними».

Как распознать BFS/DFS по условию:

• есть слова «можно перейти», «соседи», «по ребру», «вверх/вниз/влево/вправо», «из A в B»;
• нужно найти количество компонент связности (сколько отдельных групп/островков);
• нужно проверить достижимость (можно ли добраться) или построить любой путь;
• просят кратчайшее число шагов/поездок в невзвешенном графе (каждый переход стоит 1).

Суть приёма: DFS (depth-first search, «поиск в глубину») уходит как можно дальше по переходам, удобно отмечать целые компоненты. BFS (breadth-first search, «поиск в ширину») идёт слоями по расстоянию и поэтому сразу даёт минимальное число шагов в невзвешенных задачах. Оба метода ускоряют решение тем, что каждый узел/клетка обрабатывается максимум один раз: время обычно пропорционально размеру поля или числу рёбер.

С чего начать учиться:

• научиться строить соседей: 4/8 направлений в сетке, список смежности в графе;
• всегда держать массив/таблицу visited (посещено) и помечать при добавлении в очередь/стек;
• для BFS использовать очередь и хранить расстояния/родителя (для восстановления пути);
• для DFS понимать рекурсивный вариант и итеративный со стеком (чтобы не упереться в лимит рекурсии);
• отдельно потренировать: «посчитать островки», «найти кратчайший путь», «найти компоненты в ориентированном/неориентированном графе».

Ниже — задачи с автопроверкой и разбором подхода: от «островков» на сетке до кратчайших маршрутов и групп связности.