图表为什么找不到正确的路径？

Question

我试图创建图形的帮助下面的链接，但是当我使用find_path方法我得到不正确的路径返回。链接：

http://www.python-course.eu/graphs_python.php

代码：

class Graph(object): 
    def __init__(self, graph_dict=None): 
     """ initializes a graph object 
      If no dictionary or None is given, an empty dictionary will be used 
     """ 
     if graph_dict is None: 
      graph_dict = {} 
     self.__graph_dict = graph_dict 

    def find_path(self, start_vertex, end_vertex, path=[]): 
     """ find a path from start_vertex to end_vertex 
      in graph """ 
     graph = 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 

g = {"a": ["c", "d"], 
    "b": ["a", "c"], 
    "c": ["a", "b", "c", "d", "e"], 
    "d": ["c", "e"], 
    "e": ["c", "f"], 
    "f": ["c"] 
    } 

graph = Graph(g) 

""" 
graph: 

a<----b   <-- one way 
|\ /  --- two way 
| \/
| c <-- f 
|/\ ^
v/ \ | 
d---->e--/ 

""" 
print graph.find_path("b", "f") 

Output: ['b', 'a', 'c', 'd', 'e', 'f'] 
Should be: ['b', 'a', 'd', 'e', 'f'] 

什么是错在Graph类find_path方法？

Answer 1

您的代码通过跟踪每个节点的邻接列表中尚不属于该图形的第一个节点来查找路径。它从'b'开始，然后转到邻接列表（['a', 'c']）节点'a'中的第一个节点。然后它从'a'到'c'。一旦它在'c'，它看到'a','b'和'c'已经在路径中，因此它将转到'd'。如果您在图表中这改变了你的邻居列表的顺序，它会打印出你想要的顺序：

g = {"a": ["d", "c"], 
    "b": ["a", "c"], 
    "c": ["a", "b", "c", "d", "e"], 
    "d": ["e", "c"], 
    "e": ["f", "c"], 
    "f": ["c"] 
    } 

另外，还可以实现最短路径算法，如Djikstra's找到通过最短路径一张图。

Answer 2

您编程设置为找到任意非循环路径，并返回它找到的第一个。它找到的路径是完全合理的;这根本不是最少的步骤。

要找到最短路径，您需要实现宽度优先搜索或带记忆的深度优先搜索（记录每个节点的最佳已知路径）。 Dijkstra的算法适用于最短路径。