python - 在图中查找路径

Question

我正在尝试学习Python，几周前就开始了。我今天在阅读有关图表的内容时发现了以下代码:

class Graph(object):
    def __init__(self, graph_dict=None):
        if graph_dict == None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    def find_path(self, start_vertex, end_vertex, path=None):
        """Find a path from start_vertex to end_vertex in graph."""
        if path == None:
            path = []

        graph = self.__graph_dict
        print(self.__graph_dict)

        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return path
        if start_vertex not in graph:
            return None
        for vertex in graph[start_vertex]:
            if vertex not in path:
                extended_path = self.find_path(vertex, end_vertex, path)
                if extended_path:
                    return extended_path
        return None


if __name__ == "__main__":
    g = {"a" : ["c"],
         "b" : ["c", "e"],
         "c" : ["b", "d", "e"]}

    graph = Graph(g)

    graph.find_path("a", "d")

这里我打印时无法理解打印(self.__graph_dict)我得到以下打印输出:

{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}

我无法理解为什么它重复 5 次而不是仅仅一次(这是图表的字典值)。它还有什么意义吗？我在这里错过了什么吗？预先感谢您的宝贵意见和时间。

Answer 1

由于您递归调用 find_path，因此您打印了 5 次。

查看代码:

for vertex in graph[start_vertex]:
    if vertex not in path:
        extended_path = self.find_path(vertex, end_vertex, path) #this is being hit 4 times

就您的代码是否工作而言，我不认为这是一个问题。我觉得很有道理。