DFS посещает все вершины?

Question

Я только что узнал о DFS / BFS в своем классе на Python, и я не уверен, что полностью понимаю некоторые различия. В одном из упражнений впоследствии они различают DFS и DFS по кратчайшему пути. Поскольку видео на самом деле не касалось этого, я пытался понять это сам и столкнулся с некоторыми проблемами.

Я смотрю на график вот так. Допустим, я хочу посмотреть, есть ли путь между 1 и 5. Если я реализую это, не беспокоясь о поиске кратчайшего пути, остановится ли выполнение, когда он найдет узел 5? Другими словами, узлы 6-11 никогда не будут посещены. Я уверен, что это то, что я мог бы написать, но я не был уверен, что это больше не считается DFS.

Answer 1

В случае, если вы используете DFS в качестве алгоритма кратчайшего пути, этот алгоритм DFS может или не может быть правильным при поиске кратчайшего пути. Другими словами, DFS не гарантирует увеличение порядка поиска. Это происходит из-за рекурсивного характера DFS: он сначала посещает «самые глубокие» узлы, прежде чем вернуться, чтобы посетить не посещенных соседей из посещенных вершин. Чтобы получить алгоритм кратчайшего пути, лучше рассмотреть BFS, потому что он перемещается в возрастающем порядке расстояния от исходного узла. Помните, что BFS можно использовать только для невзвешенных графиков.

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

Answer 2

Ответ в том, что это зависит.

Для DFS вы пишете функцию, которая произвольно выбирает одного из ее потомков и рекурсивно вызывает себя для этого потомка. Рекурсивный вызов делает то же самое. Когда детей нет, вы поднимаетесь на один уровень выше в своей рекурсии, выбираете другого ребенка и возвращаетесь вниз.

На узле 2 в вашем дереве DFS не знает, насколько глубока какая-либо ветвь, и он может выбрать расширение узла 3 или узла 6. Если он расширяет узел 3, то он никогда не будет расширять узел 6, потому что он будет искать все под узлом 3 перед возвратом к узлу 2.

Точно так же, если Узел 1 выбирает Узел 8 перед Узлом 2, тогда Узел 11 должен быть исследован, потому что все в ветви Узла 8 должно быть исследовано прежде, чем будут исследованы любые другие ветви.

(Многие реализации DFS выбирают порядок, в котором они исследуют дочерние структуры, но это не является основным компонентом обхода. Ключевое свойство заключается в том, что после выбора узла каждый узел под этим узлом должен быть пройден до того, как любой другой дочерний элемент этого узла может быть посещен.)