如何从递归函数中获取 return 值而不是打印到控制台？

Question

我想获取图中两个节点 i 和 j 之间的所有路径。我正在使用 DFS 来完成此操作。该代码有效。但是，我不想 print 控制台的路径（请参阅 searchPaths(self, i, j, visited, path) 函数中的 print(path) 行）。我想 return 它。但是，因为它是一个递归函数，所以 return 不起作用。 return path 的正确方法是什么，以便我可以将其用于其他计算？

class Graph:
    def __init__(self, edges=dict()):
        '''Initializes a Graph. Variables:
            - edges: dictionary with edge tuples as keys (i,j) and
            weight w_ij as values.'''
        self.edges = edges


    def searchPaths(self, i, j, visited, path):
        '''Searches all possible paths from node i to node j.'''
        # Set current node as visited and store it in path 
        visited[i] = True 
        path.append(i)
        # If current node is not same as destination, recursively
        # search adjacent nodes.        
        if i != j:
            for u in self.adjacencyList[1].get(i, []):
                if visited[u] == False:
                    self.searchPaths(u, j, visited, path)
        else:
            print(path)
        # Remove current vertex from path and mark as unvisited
        path.pop()
        visited[i] = False


    def printAllPaths(self, i, j):
        '''Print all possible paths from node i to node j.'''
        # Set all nodes as not visited 
        visited = {n: False for n in self.nodes}
        # Create a list to store the path 
        path = []
        # Call recursive function to search for paths
        self.searchPaths(i, j, visited, path)

    @property
    def adjacencyList(self):
        '''Returns the adjacency list.'''
        ingoing, outgoing = {}, {}
        for edge in self.edges.keys():
            i, j = edge[0], edge[1]
            outgoing[i] = outgoing.get(i, []) + [j]
            ingoing[j] = ingoing.get(j, []) + [i]
        ingoing = {k:set(v) for k,v in ingoing.items()}
        outgoing = {k:set(v) for k,v in outgoing.items()}
        return ingoing, outgoing

作为激励示例，可以使用以下边：edges = {(1, 2): 1, (2, 1): 2, (2, 3): 2, (3, 2): 3, (3, 5): 2, (5, 4): 8, (5, 6): 9, (7, 6): 4, (7, 8): 4, (8, 9): 1, (8, 10): 3, (9, 10): 2, (10, 7): 5, (10, 11): 8, (12, 13): 3, (13, 14): 1, (14, 12): 2, (15, 14): 4}。当搜索从 i=7 到 j=11 的路径时，应该得到两条路径：[7,8,9,10,11] 和 [7,8,10,11].

Answer 1

让我们看看是否可以完成这项工作。

分析你的代码

这很奇怪：为什么要将节点标记为未访问过？这可能不会改变任何东西，或者更糟的是甚至可能导致您的代码出现问题。

# Remove current vertex from path and mark as unvisited path.pop() visited[i] = False

目标定义

我们希望：

最后一次调用 return 路径。
作为中继信息的桥梁的中间呼叫（return所有路径）

尝试

class Graph:
    def __init__(self, edges=dict()):
        '''Initializes a Graph. Variables:
            - edges: dictionary with edge tuples as keys (i,j) and
            weight w_ij as values.'''
        self.edges = edges
        self.get_nodes()

    def get_nodes(self):
        self.nodes = set()
        for i,j in self.edges:
            self.nodes.add(i)
            self.nodes.add(j)

    def searchPaths(self, i, j, visited, path):
        '''Searches all possible paths from node i to node j.'''
        # Set current node as visited and store it in path 
        visiting = dict(visited)
        visiting[i] = True 
        aux = path[:]
        aux.append(i)
        # If current node is not same as destination, recursively
        # search adjacent nodes. 
        all_paths=[]
        if i != j:
            for u in self.adjacencyList[1].get(i, []):
                if visiting[u] == False:
                    all_paths += self.searchPaths(u, j, visiting, aux)

        else:
            print(aux)
            all_paths += [aux[:]]
        return all_paths



    def printAllPaths(self, i, j):
        '''Print all possible paths from node i to node j.'''
        # Set all nodes as not visited 
        visited = {n: False for n in self.nodes}
        # Create a list to store the path 
        path = []
        # Call recursive function to search for paths
        return self.searchPaths(i, j, visited, path)

    @property
    def adjacencyList(self):
        '''Returns the adjacency list.'''
        ingoing, outgoing = {}, {}
        for edge in self.edges.keys():
            i, j = edge[0], edge[1]
            outgoing[i] = outgoing.get(i, []) + [j]
            ingoing[j] = ingoing.get(j, []) + [i]
        ingoing = {k:set(v) for k,v in ingoing.items()}
        outgoing = {k:set(v) for k,v in outgoing.items()}
        return ingoing, outgoing

如何从递归函数中获取 return 值而不是打印到控制台？

How to return value from recursive function instead of printing to console?

depth-first-search

python-3.x