递归生成图- 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并工作，但是，退出函数就像返回一样。我想知道我如何改进我的代码，使它工作，2)为什么我的逻辑是错误的。例如，我知道它产生了DC，但我对如何绕过它感到困惑。或者索引返回的值？

Answer 1

几件事：

• 格式化:将图形放在一行上是很糟糕的。
• 函数失败的原因是递归函数返回字符串或无，但是字符串和None之间的连接没有定义。始终确保递归函数要么总是返回给定的数据类型，要么总是什么都不返回。
• 除非可以清晰地调用递归函数，否则使用助手函数隐藏不必要的变量初始化。
• val变量是不必要的；节点本身没有一个循环(它没有正确地阻止这种情况)。
• 为什么要打印函数调用？您正在调用函数来发现路径，但它不返回它们。
• 为什么要写入全局变量？多次运行该函数将累积不相关的路径。
• 为什么函数不返回原始调用？

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

我还嵌套了helper函数，以便在不使用堆栈的情况下提供一个干净的调用接口，但也可以向局部变量提供平面返回结构。

这种结构也更容易看出路径是如何扩展的；也就是说，path始终是一个字符串列表，而我总是一个字符串，所以将封装成list的列表连接起来总是有效的。

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']]

如果这是作业..。很明显你不能这么做，但使用imho要容易得多.

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']