1

这是我现在的代码：

  hasht= {"A":["B", "D", "E"], "B":["C"], "C":["D", "E"], "D":["C", "E"], "E":["B"]}
   paths=[]
   def recusive(start, finish, val):
      if start==finish and val!=1:
        return start
    else:
        for i in hasht[start]:
            path= start+ recusive(i,finish,2)
            paths.append(path)
print (recusive("C","C",1))
print paths

期望的输出：[CDC, CDEBC, CEBC]

我正在尝试生成一个像上面那样的表，但是我遇到了字符串和数组没有被连接的问题。当我刚刚返回时，它会返回CDC并工作，但它会退出函数，因为 return 意味着这样做。我想知道如何在这里改进我​​的代码以使其正常工作并找出我的逻辑错误的原因。例如，我知道它会生成 say [DC]，但我对如何解决这个问题感到困惑。也许索引返回的值？然而这也不起作用！我只是对如何让路径返回CDC，然后继续下一个感到困惑。

4

1 回答 1

0

在 Python 中使用递归时需要小心一点，因为递归深度的预设限制非常低，如果递归太深，您将开始收到RuntimeError: maximum recursion depth exceeded in cmp之类的错误。

当我尝试运行您的代码时，出现错误：TypeError: cannot concatenate 'str' and 'NoneType' objects。这是因为该函数仅在start == finish时返回一个值，即在您的示例中再次到达“C”时。因为函数的else部分没有返回，所以它返回特殊值None，如果 start != end。Python 不允许您将None添加到字符串中，这解释了错误。

下面的代码完成了我认为您正在尝试做的事情，即返回从startNode到endNode的所有路径的列表。我在这里将图形作为输入参数，并返回路径列表。它需要 2 个附加参数allPaths和pathSoFar来跟踪所有路径的列表和当前路径。这只是作为如何使用递归来实现此目的的示例。这段代码有几个问题：

1) 它使用递归，正如我之前所说，这在 Python 中不是一个好主意，除非您增加预设限制。

2）它不能正确处理循环。如果图中有循环，则此函数将继续运行，直到达到递归限制。尝试使用A作为开始和结束节点运行它以查看此内容。

    def generatePaths(theGraph, startNode, endNode, allPaths, pathSoFar=""):
        """
        Recursive function. Finds all paths through the specified
        graph from start node to end node. For cyclical paths, this stops
        at the end of the first cycle.
        """
        pathSoFar = pathSoFar + startNode

        for node in theGraph[startNode]:

            if node == endNode:
                allPaths.append(pathSoFar + node)
            else:
                generatePaths(theGraph, node, endNode, allPaths, pathSoFar)




    graph = {"A":["B", "D", "E"], "B":["C"], "C":["D", "E"], "D":["C", "E"], "E":["B"]}
    paths = []
    generatePaths(graph, "C", "C", paths)
    print paths
于 2013-10-23T16:13:15.207 回答