Комментарии 5
В чем его отличие от обхода в глубину?
Капитан Очевидность напоминает: отличие в том, что DFS использует стек, а BFS - очередь. В остальном один и тот же алгоритм. Потому пишется одна реализация, которая дополнительно принимает на вход интерфейс с методами push и pop. Подставляем queue/stack/heap - работает как BFS/DFS/UCS. А рекурсивный DFS - это ересь, которую удобно искоренять с помощью графа в виде километрового связного списка.
искоренять с помощью графа в виде километрового связного списка
А мы по нему оптимизацией хвостовой рекурсии вдарим! :)
Вы полностью правы.
Но здесь есть один тонкий момент, если мы говорим о графах с циклами. Насколько помню, в DFS мы помечаем вершину как пройденную после посещения очередной вершины, а в BFS - перед посещением (добавлением в очередь).
А список смежности на первом синем рисунке в первой строке точно 0-1-2-3?
Фи, код картинками. Хабр вполне нормально отображает код. Не поленитесь и исправьте. Для одного алгоритма код на каком-то псевдокоде, а для другого — на C++. Стоит использовать везде одно и то же.
Далее, алгоритмы вы привели, а очень важные их свойства даже не упоминули. Как-то, DFS в итоге строит ориентированное от корня дерево в графе, а все остальные ребра в графе могут идти только от вершины к ее предку в дереве (но никак не связывать соседние ветки). BFS разбивает граф на слои так, что ребра есть только между соседними слоями и внутри слоев.
Обход графа в ширину (BFS) и глубину (DFS)