查找可能路径数的递归函数错误

Question

我正在使用嵌套字典来指示图形的顶点和边，例如：

[ 
A: [B,D,E],
B: [C],
C: [D,E],
D: [C,E],
E: [B]
]

到目前为止，这是我的代码：

def number_of_trips(self, start_point, end_point, maxstops):
    return self._find_path(start_point, end_point, 0, 0, maxstops)

def _find_path(self, point_a, end_point, current_stops, routes, maxstops):
    current_stops += 1

    if current_stops > maxstops:
        return routes

    if end_point in self.digraph[point_a]:
        return routes + 1
    else:
        for x in self.digraph[point_a]:
            return self._find_path(x, end_point, current_stops, routes, maxstops)

    return routes

方法是这样调用的：

number_of_trips('C', 'C', 3)

输出 1 而不是 2。

我的递归函数有什么问题？

Answer 1

在进行递归调用时增加 routes 值：

return self._find_path(x, end_point, current_stops, routes + 1, maxstops)

Answer 2

问题已通过以下代码解决：

def _find_path(self, point_a, end_point, current_stops, routes, maxstops):
        current_stops += 1

        if current_stops > maxstops:
            return routes

        if end_point in self.digraph[point_a]:
            return 1
        else:
            for x in self.digraph[point_a]:
                routes += self._find_path(x, end_point, current_stops, routes, maxstops)

        return routes

查找可能路径数的递归函数错误

Wrong recursive function to find number of possible routes

python

recursion

directed-graph