DFS вместо BFS: почему путь получается длиннее минимального
В невзвешенном неориентированном графе нужно найти минимальное число рёбер между вершинами A и B. Разработчик написал обход в глубину, который останавливается на первом достижении B и возвращает длину пройденного пути. Тесты показывают, что иногда возвращается число больше минимального.
В чём причина и как правильно?
- Достаточно помечать вершину посещённой при входе, а не при выходе — тогда DFS начнёт давать кратчайший путь
- DFS для этой задачи корректен, а число больше минимального получается только на несвязном графе
- DFS уходит вглубь по первой ветке и фиксирует первый найденный путь, а не кратчайший; нужен BFS
- Без весов не работают ни BFS, ни DFS: нужна Дейкстра с весами, равными единице