Ошибка в реализации алгоритма рекурсивной глубины первый в Python

Question

Я делаю некоторые практические проблемы на udacity и должен написать рекурсивный код, чтобы найти путь к друзьям в узле. И я придумал это. Однако в рекурсивном определении отсутствует условие остановки, я думаю, что соединение не найдено. Как мне это исправить?

def path_to_friend(network, user_A, user_B,traversed = None):
    if traversed is None:
        traversed = []

    if (user_B in network and user_A in network):
        if user_B in get_connections(network,user_A):
            return [user_A] + [user_B]
        else:
            for conn in get_connections(network,user_A) :
                if conn in traversed:
                    continue
                else:
                    traversed.append(conn)
                    return [user_A] + path_to_friend(network,conn,user_B)
    else:
       return None

структура данных сети: {'Боб': [['Кэрол'], []], 'Алиса': [['Боб'], []], 'Кэрол': [['Боб'], []]}

Найти: path_to_friend(сеть, "Боб", "Алиса")

Результат: бесконечная рекурсия. Как мне это исправить?

Answer 1

Эта строка кода здесь может вызвать проблему:

return [user_A] + path_to_friend(network,conn,user_B)

По сути, этот код запускается, как только обнаруживается какое-либо соединение, которое еще не посещалось. Таким образом, код будет искать соединение по первому не посещенному пути, а не по другому пути.

         c ---- e
        /
a ---- b
        \
         d

Если вы начинаете с a, а target-node - e, ваш код достигнет e, только если c появится перед d в get_connections(network , b), Иначе код закончится на d. Это поведение даже не определено / путь выполнения не заканчивается return-заявление.

Самое простое решение - просто вернуть None, если путь заканчивается без поиска узла:

for conn in get_connections(network,user_A) :
     if conn in traversed:
         continue
     else:
         traversed.append(conn)
         tmp = path_to_friend(network , conn , user_B)
         if (tmp is not None):
             return [user_A] + tmp//a matching path was found

//no matching path was found -> return none
return None

Следующая проблема с кодом: вы не сохраняете пройденный список от одного вызова к другому, таким образом, каждый раз, когда вызывается функция, traversed is None держит. Используйте список прохождения каждого вызова в качестве параметра для следующего вызова:

path_to_friend(network,conn,user_B, traversed)

Answer 2

def path_to_friend(network, user_A, user_B,traversed = None):
if traversed is None:
    traversed = []

if (user_B in network and user_A in network):
    if user_B in network[user_A][0] :
        return [user_A] + [user_B]
    else:
        for conn in network[user_A][0] :
            if conn in traversed:
                continue
            else:
                traversed.append(conn)
                temp = path_to_friend(network,conn,user_B,traversed)
                if (temp is not None):
                    return [user_A] + temp
        return None
else:
   return None


network = {'Bob': [['Carol'], []], 'Alice': [['Bob'], []], 'Carol': [['Bob'], []]}
path_to_friend(network,'Bob','Alice')