0

我尝试在以下链接的帮助下创建图形，但是当我使用 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 方法有什么问题？

4

2 回答 2

2

您的代码通过跟踪每个节点的邻接列表中不属于图中的第一个节点来查找路径。它从邻接表 ( ) 节点'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 的，以找到通过图形的最短路径。

于 2017-02-23T00:00:45.087 回答
1

您对此进行了编程以查找任何非循环路径，并返回它找到的第一个。它找到的路径是完全合理的；这根本不是最少的步骤。

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

于 2017-02-22T23:57:51.997 回答