Comments 2
В каких случаях предпочтителен тот или иной алгоритм?
В задачах поиска мостов и точек сочленения важно рассматривать вершины именно в порядке обхода DFS. Во многих задачах, решаемых динамическим программированием на поддеревьях использование дерева обхода в глубину. Если нужно найти кратчайший путь, DFS не поможет.
Иногда, при рассмотрении графов специального вида, например, графа клеточек на плоскости, BFS будет использовать значительно меньше памяти, храня только «фронт волны», следовательно, его применение будет предпочтительным.
Иногда, при рассмотрении графов специального вида, например, графа клеточек на плоскости, BFS будет использовать значительно меньше памяти, храня только «фронт волны», следовательно, его применение будет предпочтительным.
Sign up to leave a comment.
Графы для самых маленьких: BFS