Python图递归

Question

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

def path(d,consider,end,route=''):
    if consider==end:

        return route
    else:
        for e in d[consider]:
            print(e)
            route = path(d,e,end,route)
            route=str(e)+route
            print route

            return route

path(d,'a','d') 打印:

b
c
d
d
cd
bcd
Out[89]:
'bcd'

为什么它不打印'a'的第二个考虑因素，即'd'。它输出“b”的分支，但似乎没有探索“d”，即使它应该由 for 循环进行。

Answer 1

您还可以使用广度优先搜索来查找最短路径:

import collections
def path(d, consider, end):
  queue = collections.deque([consider])
  seen = []
  flag = False
  while queue:
    val = queue.popleft()
    if val == end:
      return seen
    seen.append(val)
    queue.extend([i for i in d[val] if i not in seen])
  return flag

result = path({'a':['b','d'],'b':['c'],'c':['d']}, 'a', 'd')
result = result if result else []
print(result)

输出:

['a', 'b']