DFS быстрее, чем BFS при поиске определенного узла в SSC?
Я хочу найти кратчайший путь от узла к другому узлу в Сильно Связанном Компоненте, узлы могут быть выбраны произвольно. На ум приходят два метода поиска: поиск в глубину или поиск в ширину.
Можно ли доказать, что для какой-то ситуации одно предпочтительнее другого?
Одна ситуация могла быть разреженным графом против плотного графа SCC.
2 ответа
DFS не гарантирует, что если узел 1 посещается раньше другого узла 2, начиная с исходной вершины, то узел 1 находится ближе к источнику, чем узел 2.
Это легко увидеть по рекурсивной природе DFS. Он посещает "более глубокие" узлы или вы можете сказать дальше от исходных узлов. Он идет как можно дальше от исходной вершины, а затем возвращается к не посещенным смежным узлам посещенных вершин.
С другой стороны, BFS всегда посещает узлы в порядке возрастания их расстояния от источника. Сначала он посещает все узлы на одном и том же "уровне" графика, а затем переходит на следующий уровень.
Кроме того, использование нерекурсивного алгоритма (BFS) более продуктивно с чисто практической точки зрения.
BFS сначала посещает все узлы, которые подключены к текущему узлу, поэтому каждый новый найденный узел соединяется с использованием наименьшего числа возможных ребер. С другой стороны, DFS следует за одним ребром от каждого узла до тех пор, пока не останется ребер, которым нужно следовать, что не даст вам необходимого кратчайшего пути.