在图形中寻找路径

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")

我在打印 print(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']}

我不明白为什么要重复五次，而不是只使用图表的字典值一次。这是否有任何重要意义？我是否漏掉了什么东西？感谢您宝贵的意见和时间。

- prabh

---

初始化后，您没有执行任何操作来修改图形字典。您的第一个打印语句将完全打印图形字典。此外，该函数从不修改图形字典，因此它永远不会打印除原始内容以外的任何内容。 - W4t3randWind

Answer 1

你重复调用了find_path，所以你会得到五份打印输出。

看一下代码：

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

就你的代码是否能正常工作而言，我认为这并不是问题。对我来说，它似乎很有道理。

- David Kaftan

---

另外，你正在 find_path 方法内部打印，但看起来你应该只在最后一行调用 graph.find_path 时打印。 - hdiogenes