即使这是一个有点老的问题，我还是想为遇到问题的任何人提供一个切实可行的答案。
假设您以如下的元组列表的形式获取连接的输入数据：
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]我发现对Python中的图形最有用和最有效的数据结构是 集合的决定
。这将是我们
Graph班级的基础结构。您还必须知道这些连接是弧形（定向，以一种方式连接）还是边缘（无定向，以两种方式连接）。我们将通过
directed向该
Graph.__init__方法添加参数来处理该问题。我们还将添加一些其他有用的方法。
import pprintfrom collections import defaultdictclass Graph(object): """ Graph data structure, undirected by default. """ def __init__(self, connections, directed=False): self._graph = defaultdict(set) self._directed = directed self.add_connections(connections) def add_connections(self, connections): """ Add connections (list of tuple pairs) to graph """ for node1, node2 in connections: self.add(node1, node2) def add(self, node1, node2): """ Add connection between node1 and node2 """ self._graph[node1].add(node2) if not self._directed: self._graph[node2].add(node1) def remove(self, node): """ Remove all references to node """ for n, cxns in self._graph.items(): # python3: items(); python2: iteritems() try: cxns.remove(node) except KeyError: pass try: del self._graph[node] except KeyError: pass def is_connected(self, node1, node2): """ Is node1 directly connected to node2 """ return node1 in self._graph and node2 in self._graph[node1] def find_path(self, node1, node2, path=[]): """ Find any path between node1 and node2 (may not be shortest) """ path = path + [node1] if node1 == node2: return path if node1 not in self._graph: return None for node in self._graph[node1]: if node not in path: new_path = self.find_path(node, node2, path) if new_path: return new_path return None def __str__(self): return '{}({})'.format(self.__class__.__name__, dict(self._graph))我将其作为创建读者
find_shortest_path和其他方法的“读者练习” 。
让我们来看看实际情况…
>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]>>> g = Graph(connections, directed=True)>>> pretty_print = pprint.PrettyPrinter()>>> pretty_print.pprint(g._graph){'A': {'B'}, 'B': {'D', 'C'}, 'C': {'D'}, 'E': {'F'}, 'F': {'C'}}>>> g = Graph(connections) # undirected>>> pretty_print = pprint.PrettyPrinter()>>> pretty_print.pprint(g._graph){'A': {'B'}, 'B': {'D', 'A', 'C'}, 'C': {'D', 'F', 'B'}, 'D': {'C', 'B'}, 'E': {'F'}, 'F': {'E', 'C'}}>>> g.add('E', 'D')>>> pretty_print.pprint(g._graph){'A': {'B'}, 'B': {'D', 'A', 'C'}, 'C': {'D', 'F', 'B'}, 'D': {'C', 'E', 'B'}, 'E': {'D', 'F'}, 'F': {'E', 'C'}}>>> g.remove('A')>>> pretty_print.pprint(g._graph){'B': {'D', 'C'}, 'C': {'D', 'F', 'B'}, 'D': {'C', 'E', 'B'}, 'E': {'D', 'F'}, 'F': {'E', 'C'}}>>> g.add('G', 'B')>>> pretty_print.pprint(g._graph){'B': {'D', 'G', 'C'}, 'C': {'D', 'F', 'B'}, 'D': {'C', 'E', 'B'}, 'E': {'D', 'F'}, 'F': {'E', 'C'}, 'G': {'B'}}>>> g.find_path('G', 'E')['G', 'B', 'D', 'C', 'F', 'E']
