递归图遍历:如何生成和返回所有路径? [英] Recursive graph traversal: how to generate and return all paths?

问题描述

这是我的代码:

  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的意图而退出了该函数.我想知道如何在这里改善代码以使其正常工作，并弄清楚为什么我的逻辑有问题.例如，我知道它会生成[DC]，但是我对如何解决这个问题感到困惑.也许索引返回的值?但这也不起作用！我只是对如何在CDC之后返回路径然后继续前进到下一个路径感到困惑.

I am trying to generate a table like the one above, but I am running into a problem where the string and the array are not being concatenated. When I just return, it returns CDC and works however and it exits the function as return is meant to do. I am wondering how I can improve my code here to make it work and figure out why my logic was faulty. For example, I understand that it generates say [DC], but I am confused as to how to go around that. Perhaps index the value returned? Yet that doesn't work either! I am just confused as to how to make the path return once it is CDC, and then move on to the next one.

推荐答案

在Python中使用递归时，您需要格外小心，因为递归深度的预设限制非常低，并且您将开始出现错误例如 RuntimeError:如果递归的深度过深，则最大递归深度将超出cmp .

You need to be a little careful when using recursion in Python, as the pre-set limit on recursion depth is quite low, and you'll start getting errors like RuntimeError: maximum recursion depth exceeded in cmp if you recurse too deeply.

当我尝试运行您的代码时，出现错误: TypeError:无法连接'str'和'NoneType'对象.这是因为在示例中，该函数仅在 start == finish 时(即，当您再次进入"C"时)返回值.因为该函数的 else 部分中没有 return ，所以如果start！= end，它将返回特殊值 None . Python不允许您将 None 添加到字符串中，这可以解释该错误.

When I try to run your code, I get an error: TypeError: cannot concatenate 'str' and 'NoneType' objects. This is because the function only returns a value when start == finish, i.e. when you get to 'C' again, in your example. Because there is no return in the else part of the function, it returns the special value None, if start != end. Python won't let you add None to a string, which explains the error.

下面的代码执行了我认为您要尝试的操作，即返回从 startNode 到 endNode 的所有路径的列表.我在这里将图作为输入参数，并返回路径列表.它需要两个附加参数 allPaths 和 pathSoFar 来跟踪所有路径的列表和当前路径.这仅作为如何使用递归来实现此目的的示例.这段代码有几处错误:

The code below does what I think you're trying to do, which is return a list of all paths from startNode to endNode. I've made the graph an input argument here, and the list of paths is returned. It takes 2 additional arguments, allPaths and pathSoFar, to keep track of the list of all paths, and the current path. This is only intended as an example of how to use recursion to achieve this. There are several things wrong with this code:

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

1) It uses recursion which, as I said earlier, is not a great idea in Python unless you increase the pre-set limit.

2)它不能正确处理循环.如果图中有循环，则此功能将继续进行直到达到递归限制.尝试使用 A 作为起始节点和结束节点来运行它.

2) It does not deal properly with cycles. If there are cycles in the graph, this function will just keep on going until it hits the recursion limit. Try running it with A as the start and end node to see this.

    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

这篇关于递归图遍历:如何生成和返回所有路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！