使BFS适应多个目标值

Question

我有以下功能程序函数BFS显示从节点到目标的路径/目标。如何我可以修改功能BFS，以取代单一字符作为目标吗 应接受字符列表。在

# tree stored as a dictionary (parent: [children])
simpletree = {'a':  ['b', 'c'],
              'b':  ['d','e', 'f'],
              'c':  ['g', 'h', 'i','j'],
              'd':  ['k', 'l'],
              'e':  ['m'],
              'g':  ['n'],
              'i':  ['o'],
              'j':  ['p'],
              'o':  ['z']}

def Successors(node,dictionarytree):

    children=dictionarytree[node]#extracting the children of a node

    for child in children:#i get the children using a for loop and  yield
             yield child




# Breadth-First search of a dictionary tree
def BFS(nodelist,target,dictionarytree):
    print "Nodelist:",nodelist
    childlist=[]
    # iterate over all the nodes in parentlist
    for parent in nodelist:

        # if the node is the target
        if parent[-1]==target:
            return parent
        # check if the node has children    
        if dictionarytree.has_key(parent[-1]):#check if the key exists in the  dictionary

            # loop through children and return children
             for child in Successors(parent[-1],dictionarytree): 
                    print child
                    childpath=parent+(child,)#add the targert to the childpath


                    childlist.append(childpath)
                    print "childpath",childpath
    # if there are children, progress to the next level of the tree
    if len(childlist) != 0:
        return BFS(childlist,target,dictionarytree)
    else:
        return None

node='a'
goal='z'
print simpletree
print BFS([(node,)],goal,simpletree)

Answer 1

嗯，BFS并不是真的设计成有多个目标结尾。你不能真的把它叫做BFS。如果你真的对它感兴趣，你可以把它画出来，看看如果你在精神上遵循算法会发生什么。但你需要跟踪目标的路径。我不认为这会有多大帮助。在

就个人而言，由于这看起来像是为了上学，所以我只需在另一个函数中遍历字符列表并存储这些值。您需要编辑BFS函数来返回路径，而不是打印它。在

def multipleBFSRuns(listOfChars):
  values=[]
  for x in listOfChars:
     values.append(BFS([(node,)],x,simpletree))
  return values