Итеративная прогулка по дереву

Question

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

Каковы, если таковые имеются, преимущества итеративного и рекурсивного обхода? В каких ситуациях я могу использовать один, а не другой?

Answer 1

Если вы выполняете поиск в ширину, естественная реализация заключается в том, чтобы помещать узлы в очередь, а не использовать рекурсию.

Если вы выполняете поиск в глубину, то рекурсия является наиболее естественным способом кодирования обхода. Однако, если ваш компилятор не оптимизирует хвостовую рекурсию в итерацию, ваша рекурсивная реализация будет медленнее, чем итерационный алгоритм, и умрет с переполнением стека на достаточно глубоком дереве.

Несколько быстрых Python, чтобы проиллюстрировать разницу:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))
def bfs(t):
    to_visit = [t]
    while len(to_visit) > 0:
        c = to_visit[0]
        if type(c) is int:
            print c
        else: 
            print c[0]
            to_visit.append(c[1])
            if len(c) > 2: to_visit.append(c[2])
        to_visit = to_visit[1:]

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

bfs(t)
dfs(t)

Answer 2

Если у вас есть фиксированный объем памяти, выделенный для стека, как вы часто это делаете (это особенно проблема во многих конфигурациях Java JVM), рекурсия может не сработать, если у вас глубокое дерево (или если глубина рекурсии равна высокий в любом другом сценарии); это вызовет переполнение стека. Итеративный подход, подталкивающий узлы к посещению в очередь (для BFS-подобного обхода) или в стек (для DFS-подобного обхода), имеет лучшие свойства памяти несколькими способами, поэтому, если это важно, используйте итеративный подход.

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

Answer 3

На самом деле вы должны использовать очередь для поиска в ширину и стек для поиска в глубину, и запустить ваш алгоритм из цикла while. Выполнение рекурсивных вызовов функций может значительно затянуть вашу программу, если вы делаете простые операции при обходе, и может вызвать переполнение стека, но в эти дни вы бы нужно очень стараться, чтобы увидеть один.

Просто добавьте хеш для отслеживания уже посещенных узлов, если это не так дерево, но хорошо связанный граф.

Answer 4

Это зависит от того, хотите ли вы выполнить обход в глубину или в ширину. Depth-first проще всего реализовать с помощью рекурсии. При использовании Breadth-first вам нужно сохранить очередь узлов для расширения в будущем.

Answer 5

Продолжайте с рекурсивом, потому что на самом деле вы можете получить ошибку переполнения стека, а это все-таки stackoverflow.com.