Python 返回图中所有可能路径的方法 class (DAG)

Question

我有一个关于在有向无环图中从源到目的地查找所有路径的问题。为此，我制作了两个自定义的 classes 作为 Node 和 Graph。 Graph class 读取邻近矩阵以创建节点并在字典中添加连接。
在此之后，我希望能够使用递归找到从源到目的地的所有可能路径，并使用生成器返回它们，但我在递归调用时遇到问题，因为它没有正确导航路径。
AllPathUtils 方法没有移动到第一个方法调用之后。这几乎是我的代码，如果你们中的任何一个能指出我遗漏的愚蠢错误，我将不胜感激。在底部，我将留下一些示例输入，因此您可以检查确切的行为。非常感谢。

class Node:
    def __init__(self, identity):
       self.name = identity

    def get_name(self):
        return self.name

    def __hash__(self):
        return hash(self.get_name())

    def __eq__(self, other):
       return self.get_name() == other.get_name()

    def __ne__(self, other):
        return not self == other

    def __str__(self):
        return f"Node -> {self.get_name()}"

    def __repr__(self):
        return f"Node -> {self.get_name()}"


class Graph:
    def __init__(self, matrix_graph):
        self.graph = {}
        self.V = len(matrix_graph)
        i = 0
        for node in matrix_graph:
            x = Node(i)
            self.graph[x] = []
            j = 0
            for adj in node:
                if matrix_graph[i][j] != 0:
                    self.graph[x].append(Node(j))
                j += 1
            i += 1

    def AllPathsUtil(self, u, d, visited, path):
        visited[u.get_name()] = True
        path.append(u)
        if u == d:
            yield path
        else:
            for i in self.graph[u]:
                if visited[i.get_name()] is False:
                    self.AllPathsUtil(i, d, visited, path)
        path.pop()
        visited[u.get_name()] = False

    def printAllPaths(self, s, d):
        visited = [False] * (self.V)
        path = []
        for el in self.AllPathsUtil(s, d, visited, path):
            print(el)



matrix2 = [[0, 1, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 0],
       [0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0]]

z = Graph(matrix2)
z.printAllPaths(Node(0), Node(4))

Answer 1

对于和我有同样问题的人，错误是我需要从递归调用中退出，否则它不会工作。这是有问题的行：

self.AllPathsUtil(i, d, visited, path)

虽然这是正确的：

yield from self.AllPathsUtil(i, d, visited, path)

Python 返回图中所有可能路径的方法 class (DAG)

Python method for returning all possible paths in a graph class (DAG)

python

class

path-finding

directed-acyclic-graphs