Комментарии 3
Сегодня вроде не первое апреля
Но ведь можно же взять стек и складывать вершины туда (очередь для поиска в ширину), что позволяет легко и просто избавиться от рекурсии...
Что самое интересное, этот подход и описан в начале. Конечно, рекурсия тоже использует стек в каком-то роде :)
Использовал как-то такой алгоритм, для закраски. Как правильно написали, O(V), то есть, в худшем случае, закрасив пустой лист, размером несколько мегабайт, мы потом ещё на откате просматриваем V сохранённых на стеке. То есть, сама суть как можно более глубокого погружения, говорит нам о том, что мы пройдём до упора и запомним все развилки, даже если через них будет проходить путь (например, движение змейкой). В общем, алгоритм старается отложить как можно больше на потом, того, чего откладывать и не стоило. В те временf X*Мб на стеке, было равносильно memory exception, а запомнился мне он тем, что если его потимизровать и он ничего не отложит на потом, то всё равно полная глубина выжрет самой записью вызова на стеке как минимум V. В итоге, медленный фронт волны ака поиск в ширину, кажется расточительным, но по сравнению с этим — нет.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализуем алгоритм поиска в глубину