Рекурсивный DFS против итеративного DFS

Я пытаюсь понять разницу между рекурсивной DFS и итеративной DFS. Использует ли тот, у кого есть стек, итеративный или рекурсивный подход?

Например, каковы будут результаты использования рекурсивного обхода графа в поиске в глубину и итеративного обхода графа в поиске в глубину? Соседи перебираются в алфавитном порядке.

Вот график:

введите здесь описание изображения

Для обхода DFS (тот, который со стеком, не уверен, рекурсивный он или итеративный) это то, что я получил: A, C, D, E, F. Может ли кто-нибудь подтвердить, какой это тип обхода DFS, и как другой один будет работать? Спасибо!


recursion algorithm depth-first-search
person BostonMan    schedule 20.11.2014    source источник
comment
Кстати, такие вопросы лучше задавать по адресу: cs.stackexchange.com.   -  person    schedule 20.11.2014

Ответы (2)


arrow_upward
3
arrow_downward

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

person Codor    schedule 20.11.2014
comment
Это не совсем правда. Существуют различия в результатах между рекурсивным и итеративным подходами. Подробнее см. Итеративный DFS и рекурсивный DFS и другой порядок элементов. - person amit; 20.11.2014
comment
Что ж, вы правы, однако, как упоминалось в связанном вопросе, сам по себе порядок обхода детей не указан; должен быть определен некоторый дополнительный порядок. Я немного изменю свой ответ. - person Codor; 20.11.2014

arrow_upward
0
arrow_downward

Как указано в другом ответе, обход вашего графа с использованием DFS будет посещать вершины одинаковым образом, независимо от фактической реализации DFS, с использованием итерации или рекурсии. См. псевдокод в статье Википедии.

У вас есть дополнительное требование — посетить соседние вершины в алфавитном порядке. Это означает, что стек должен быть отсортирован при отправке в него данных (в итеративной версии) или это означает, что вы должны рекурсивно работать с соседними вершинами в отсортированном порядке (в рекурсивной версии). Обе реализации будут вести себя совершенно одинаково.

Учитывая ограничение алфавитного порядка, результат A, C, D, E, F является единственным возможным обходом графа в поиске в глубину.

person Community    schedule 20.11.2014