Я правда никогда не встречал такого термина "настоящий DFS". Поделитесь, пожалуйста, если где-то кроме этой беседы он присутствует.
Возможно, если бы нам важен был порядок обхода, то имело бы место такое замечание. И нужно бы было, как говорит Википедия развернуть порядок вершин при укладывании их в стек. Но мы здесь решаем простую задачу - хотим понять, есть ли путь от одной вершины до другой. Поэтому порядок обхода нам не важен.
Можно представить себе, что в списке соседей каждого узла соседи лежат в обратном порядке, или при выборе соседей мы разворачиваем получаемый список, и тогда мы пойдём по-другому. Так, как вам кажется "по-настоящему".
По поводу поиска в глубину. Формулировка "настоящий алгоритм делает это строго по одной" не совсем ясна. Что значит "настоящий алгоритм"? Обратимся например к википедии и увидим: "Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен)."
Перехода из 11 в 7 быть не должно. Ровно по той же причине, почему нет перехода в узел 1. Ведь они лежат ниже в стеке чем узла, добавленные позднее.
По поводу алгоритма Дейкстры. Действительно, массив self.distances будет обновляться, т.к. передан в класс по ссылке, а веса внутри элементов кучи останутся старыми.
Круто! ??
конечно же можно.
Если граф имеет две компоненты связности, то мы просто не попадём из одной компоненты связности в другую, т.к. ходим только по рёбрам.
И ещё раз повторю. Мы здесь решаем другую задачу - поиск пути в графе.
Я правда никогда не встречал такого термина "настоящий DFS". Поделитесь, пожалуйста, если где-то кроме этой беседы он присутствует.
Возможно, если бы нам важен был порядок обхода, то имело бы место такое замечание. И нужно бы было, как говорит Википедия развернуть порядок вершин при укладывании их в стек. Но мы здесь решаем простую задачу - хотим понять, есть ли путь от одной вершины до другой. Поэтому порядок обхода нам не важен.
Можно представить себе, что в списке соседей каждого узла соседи лежат в обратном порядке, или при выборе соседей мы разворачиваем получаемый список, и тогда мы пойдём по-другому. Так, как вам кажется "по-настоящему".
Не уверен, что это так. По крайней мере никогда не встречал такого утверждения, что рекурсивный - настоящий, а итеративный - ненастоящий.
По поводу поиска в глубину. Формулировка "настоящий алгоритм делает это строго по одной" не совсем ясна. Что значит "настоящий алгоритм"? Обратимся например к википедии и увидим: "Кладём в стек всех её белых соседок в порядке, обратном порядку обхода (если таковой важен)."
Перехода из 11 в 7 быть не должно. Ровно по той же причине, почему нет перехода в узел 1. Ведь они лежат ниже в стеке чем узла, добавленные позднее.
По поводу алгоритма Дейкстры. Действительно, массив
self.distancesбудет обновляться, т.к. передан в класс по ссылке, а веса внутри элементов кучи останутся старыми.