Словарь рекурсии и Python

Question

Я работаю над курсом «Удипс» в области компьютерных наук.

Для набора проблем мне нужно определить, является ли ссылка взаимной. Ссылка из A -> B считается обратной, если есть k звеньев из B -> A.

Например. если k = 2, B-> A будет считаться обратной связью для узла A, если есть путь A-> C-> B для некоторой страницы C (путь прохождения по длине 2), или прямая ссылка A-> B (путь прохождения длины 1).

Вот «Интернет», который я использую для решения этой проблемы. Это просто диктовка, где ключ - это URL, а значение - список ссылок на этой странице.

g = {'a': ['a', 'b', 'c'], 'b':['a','e'], 'c':['d'], 'd':['a'], 'e':['c']} 

Теперь здесь вспомогательная функция я работаю, что в идеале будет возвращать логическое значение в зависимости от того, LINK_A -> link_b взаимна.

def is_reciprocal(g,link_a,link_b,k): 
    """ 
    Returns True if link_a --> link_b is reciprocal 
    """ 
    url_links = [] 
    print " " 
    print "link_a is...",link_a 
    print "link_b is...",link_b 
    print "k is...",k 
    print 
    if k == -1: 
     return False 
    for i in g[link_b]: 
     if i == link_a: 
      return True 

    return is_reciprocal(g,link_a,g[link_b][0],k-1) 

Вот тестовое значение, которое я делаю.

t1 = is_reciprocal(g1,'e','c',4) 

Что печатает ...

link_a is... e 
link_b is... c 
k is... 4 


link_a is... e 
link_b is... d 
k is... 3 


link_a is... e 
link_b is... a 
k is... 2 


link_a is... e 
link_b is... a 
k is... 1 


link_a is... e 
link_b is... a 
k is... 0 


link_a is... e 
link_b is... a 
k is... -1 

Кажется, что когда link_b является 'a', то же link_b продолжает привыкания.

Мой вопрос:
Есть ли способ рекурсивно перебирать это dict и сделать link_b эквивалент ко всем значениям в g['a'], сохраняя при этом значение k то же самое?

Answer 1

Похоже, что когда link_b является 'a', тот же link_b продолжает привыкать.

Это не удивительно, учитывая, что ваш рекурсивный вызов явно использует только первое значение:

return is_reciprocal(g,link_a,g[link_b][0],k-1) 

Если вы хотите использовать все значений, вам нужно рекурсию на каждом из значения, пока один из них не будет истинным. Например:

for i in g[link_b]: 
    if is_reciprocal(g,link_a,i,k-1): 
     return True 

Однако вы можете заметить, что теперь у вас есть две почти одинаковые петли подряд. Если вы измените свой рекурсивный базовый футляр для обработки флага i == link_a (что тривиально: вместо возврата False, если k == -1, просто верните link_a == link_b, если k == 0), то вы можете удалить первый цикл и получить только второй.