Рекурсивная функция Python DFS, сохраняющая значения из предыдущего вызова - PullRequest
Новая
       44

Рекурсивная функция Python DFS, сохраняющая значения из предыдущего вызова

0 голосов
/ 07 января 2019

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

Вот что происходит: 

def rec_dfs(g, start_node, visited=[]):
    visited.append(start_node)
    for next_node in g[start_node]:
        if next_node not in visited:
            rec_dfs(g, next_node, visited)
    return visited

graph2={'A': ['B', 'C', 'D'],
       'B': ['A', 'E', 'F'],
       'C': ['A', 'F'],
       'D': ['A'],
       'E': ['B'],
       'F': ['B', 'C']}

rec_dfs(graph2, "A") #['A', 'B', 'E', 'F', 'C', 'D']               OK
rec_dfs(graph2, "A") #['A', 'B', 'E', 'F', 'C', 'D', 'A']          NOK
rec_dfs(graph2, "A") #['A', 'B', 'E', 'F', 'C', 'D', 'A', 'A']     NOK

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

Если я вызываю функцию как: 

rec_dfs(graph2, "A", []) #['A', 'B', 'E', 'F', 'C', 'D']  OK
rec_dfs(graph2, "A", []) #['A', 'B', 'E', 'F', 'C', 'D']  OK
rec_dfs(graph2, "A", []) #['A', 'B', 'E', 'F', 'C', 'D']  OK

работает просто отлично ...
Я был бы очень признателен, если бы кто-то мог объяснить, почему такое поведение происходит, и если есть способ избежать этого.

Спасибо!

1 Ответ

0 голосов
/ 07 января 2019

Вы используете массив visited в качестве изменяемого аргумента по умолчанию, который по существу инициализируется пустым массивом только один раз при определении согласно http://code.activestate.com/recipes/577786-smarter-default-arguments/.

Во время каждого последующего вызова rec_dfs(), если массив visited явно не инициализирован повторно, он будет поддерживать свое состояние при каждом последующем вызове функции.

...