记住内部递归函数的深度Class

Question

为了让我的小脚本正常工作，我需要记住 class.

中每个递归函数的深度

假设我们有一个这样的依赖列表：

package1:
package2: package1
package3: package1 | package2

这只是意味着 package1 不依赖于任何东西，package2 依赖于 package1 而 package3 依赖于 package1 或者 package2.

我在尝试在 class 中实现计数器时发现了问题。递归部分包括进入当前节点（self），将计数器递增 1，调用前一个节点等等，直到图的顶部。我需要计算深度，因为在或中我需要选择依赖性较低的包，在这种情况下 package1 因为它没有依赖性。

我尝试的是以下操作：

class Node:
...
counter = 0
def dep_resolve(self, resolved, unresolved):
    unresolved.append(self)
    counter += 1
    for edge in self.edges:
        if edge not in resolved:
            if edge in unresolved:
                raise Exception('Circular')
            edge.dep_resolve(resolved, unresolved)
    resolved.append(self)
    unresolved.remove(self)

相同，但计数器在 Class 之外；

counter = 0
class Node:
...

并将计数器作为全局变量。但我仍然收到错误消息((ie.UnboundLocalError: local variable 'counter' referenced before assignment))

是否有正确的方法来记住 class 中的依赖关系？

Answer 1

您可以在其他位置解决此问题。

您的包和依赖项基本上是一个 graph，其中包是顶点，依赖项是边。

您的方法基本上是 DFS on this graph, which is fine, and can find the depth of each package (though if it's not a tree - 您可能会发现不是最短的深度）。

另一种旨在找到 "shortest path"（或您的情况下的最小深度）的方法是运行和 BFS。
这样维护BFS的当前深度非常容易，所有深度为k的包都会在算法中一起开发，所以使用这种方法很容易找到深度.

python-类似 BFS 方法的伪代码：

q = new queue
q.add((source,0))
visited = {}
visited[source] = 1
while not q.empty():
    (curr,d) = q.poll()
    for each dependency (curr,next):
        if next not in visited:
             visited[next] = 1
             q.add(next,d+1)
             #the depth of next is d+1, do something with it

记住内部递归函数的深度Class

Memorising Depth of Recursive Function Inside Class

algorithm

recursion

class

depth

python-3.x