0

这是我现在的代码：

   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 意味着这样做。我想知道如何在这里改进我​​的代码以 1）使其工作，2）为什么我的逻辑有问题。例如，我知道它会生成说 [DC]，但我对如何绕过它感到困惑。也许索引返回的值？

4

3 回答 3

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")
于 2013-10-23T02:24:18.923 回答
1

为什么不只使用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']]

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

于 2013-10-23T14:00:36.670 回答
0

这里的主要问题是，当您到达内部 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']
于 2013-10-23T03:06:40.607 回答