DFS быстрее, чем BFS при поиске определенного узла в SSC?

Question

Я хочу найти кратчайший путь от узла к другому узлу в компоненте с сильными связями, узлы могут быть выбраны произвольно. На ум приходят два метода поиска: поиск в глубину или поиск в ширину.
Можно ли доказать, что для какой-то ситуации одно предпочтительнее другого?
Одна ситуация может быть разреженным графом против плотного графа SCC.

Answer 1

BFS сначала посещает все узлы, которые подключены к текущему узлу, поэтому каждый новый найденный узел подключается с использованием наименьшего числа возможных ребер. С другой стороны, DFS следует за одним ребром от каждого узла до тех пор, пока не останется ребер, которым нужно следовать, не давая вам необходимого кратчайшего пути.

Answer 2

DFS не гарантирует, что если узел 1 посещается раньше другого узла 2, начиная с исходной вершины, то узел 1 находится ближе к источнику, чем узел 2.

Это легко увидеть по рекурсивной природе DFS. Он посещает «более глубокие» узлы или вы можете сказать дальше от исходных узлов. Он идет как можно дальше от исходной вершины, а затем возвращается обратно в не посещенные смежные узлы посещенных вершин.

С другой стороны, BFS всегда посещает узлы в порядке возрастания их расстояния от источника. Сначала он посещает все узлы на одном и том же «уровне» графика, а затем переходит на следующий уровень.

Кроме того, использование нерекурсивного алгоритма (BFS) более продуктивно с практической точки зрения.