递归生成图形 - Python

Question

这是我现在的代码：

   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 并正常工作，但是，退出函数就像返回一样。我想知道如何在这里改进我的代码以 1） 使其工作，2） 为什么我的逻辑有问题。例如，我知道它生成说 [DC]，但我对如何解决这个问题感到困惑。也许索引返回的值？

Answer 1

有几件事：

• 格式：将图形放在一条线上很糟糕
函数
• 失败的原因是递归函数返回字符串或 None，但字符串和 None 之间的串联未定义。始终确保递归函数始终返回给定的数据类型或始终不返回任何内容。
• 除非可以干净地调用递归函数，否则请使用帮助程序函数隐藏不必要的变量初始化。
• val 变量是不必要的;没有一个节点循环到自己（无论如何它不能正确地阻止它）
• 为什么要打印函数调用？您正在调用函数来发现路径，但它不会返回它们。
• 为什么要写入全局变量？多次运行该函数会将不相关的路径累积在一起。
• 为什么该函数不返回任何原始调用？

我将函数更改为传递路径变量而不是开始变量，因为递归函数在不返回数据而是写入变量（路径列表）时更容易理解（这是嵌套辅助函数的另一个好处）。

我还嵌套了帮助程序函数，以便提供一个干净的调用接口，但也提供局部变量的平面返回结构，而无需使用堆栈。

这种结构也更容易看到路径是如何扩展的;也就是说，path 始终是字符串列表，i 始终是字符串，因此将列表封装的字符串连接到列表将始终有效。

hasht = 
{
    "A" : ["B", "D", "E"],
    "B" : ["C"],
    "C" : ["D", "E"], 
    "D" : ["C", "E"], 
    "E" : ["B"]
}
def recursive(start, finish):
    paths=[]
    def recursive_helper(path, finish):
        for i in hasht[path[-1]]:
            if i == finish:
                paths.append(path + [i])
                continue
            else:
                recursive_helper(path + [i], finish)
    recursive_helper([start], finish)
    return paths
print recursive("C", "C")

Answer 2

为什么不直接使用networkx？ 这就是它的用途...

hasht = 
{
    "A" : ["B", "D", "E"],
    "B" : ["C"],
    "C" : ["D", "E"], 
    "D" : ["C", "E"], 
    "E" : ["B"]
}
import networkx as nx
G = nx.DiGraph(hasht)
list(nx.all_simple_paths(G, 'C', 'C'))
[['C', 'E', 'B', 'C'], ['C', 'D', 'C'], ['C', 'D', 'E', 'B', 'C']]

如果这是家庭作业...那么显然你不能这样做，但恕我直言，使用起来要容易得多......

Answer 3

这里的主要问题是，当您到达内部 for 循环的末尾时，您不会返回任何内容。因此，从上一个递归返回 NoneType 导致您的错误：

让我们浏览一下您的代码，看看会发生什么：我们将通过在列表中替换 for 循环来做到这一点，这样我们就可以完全看到发生了什么（这不是有效的 python 代码，仅用于演示目的:D）

rec('C','C',1)
for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['C','E']
    path_j = 'D' + rec('C','C',2)
      'C'=='C' and 2!=1
       return 'C'

好的，到目前为止一切顺利，我们有路径（path_j）"DC"，所以我们将其附加到路径，现在查看j现在设置为"E"的最内层循环

rec('C','C',1)
for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['E']
    path_j = 'D'+rec('E','C',2)
    for k in ['B']
      path_k = 'B'+rec('B','C',2)
      for l in ['C']
          'C'=='C' and 2!=1
           return 'C'

好的，我们有另一条路。这次是 path_k = 'BC'，所以让我们将其附加到路径中。但是现在我们已经用完了 k 的元素，我们需要返回一些东西

rec('C','C',1)
for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['E']
    path_j = 'D'+rec('E','C',2)
    for k in []
        return ???

目前你什么都不返回，所以python为你返回一个'NoneType'对象

rec('C','C',1)
for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['E']
    path_j = 'D'+NoneType

不幸的是，您现在正在尝试将此NoneType与字符串连接起来，因此您的错误：

TypeError: cannot concatenate 'str' and 'NoneType' objects

为了更正，您可以只返回路径字符串：（这是现在实际有效的python代码）

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)
    return path
print (recusive("C","C",1))
print paths

这将返回路径：

['DC', 'BC', 'EBC', 'DEBC', 'CDEBC', 'BC', 'EBC', 'CEBC']