在Python中表示图形（数据结构）

本文介绍了在Python中表示图形（数据结构）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如何在图 ：//en.wikipedia/wiki/Python_（programming_language）rel =noreferrer> Python ？ （从零开始，即没有库！）什么数据结构（例如dicts / tuples / dict（tuples））将是快速的，但是也是高效的内存？一个必须能够做各种图操作。可以帮助各种图表表示。在Python中如何实现它们？ 对于图书馆，这个问题有很好的答案。

谢谢！

解决方案

即使这是一个有点古老的问题，我以为我会为任何绊脚石的人提供一个实际的答案。

我们假设你得到你的连接的输入数据如下所示的元组列表：

[（'A'，'B'），（'B'，' ），（'B'，'D'），（'C'，'D'），（'E'，'F'），（'F'，'C'）]

我发现对Python中图形最有用和最有效的数据结构是集合 。这将是我们的 Graph 类的基础结构。您还必须知道这些连接是否为弧（定向，单向连接）或边缘（无向，双向连接）。我们将通过在 Graph .__ init __ 方法中添加定向参数来处理。我们还将添加一些其他有用的方法。

从集合import defaultdict class Graph（object）：图形数据结构，默认无方向。 def __init __（self，connections，directed = False）： self。 _graph = defaultdict（set） self._directed = directed self.add_connections（connections） def add_connections（self，connections）：添加连接（元组列表）到图形 为node1，node2在连接中： self.add（node1，node2） def add（self ，node1，node2）：添加node1和node2之间的连接 self._graph [node1] .add（node2）如果不是self._directed ： self._graph [node2] .add（node1） def remove（self，node）：删除所有引用节点 为n，cxns在self._graph.iteritems（） ： try： cxns.remove（node）除了KeyError： pass try： del self._graph [node] 除了KeyError： pass def is_connected（self，node1，node2）：node1直接连接到node2 在self._graph [node1]中的self._graph和node2中返回node1 def find_path（self，node1，node2，path = []）：查找node1之间的任何路径和node2（可能不是最短的） path = path + [node1] 如果node1 == node2：返回路径如果node1不在self._graph： return none for self._graph [node1]中的节点：$ b​​ $ b如果节点不在路径中： new_path = self.find_path（node，node2，path） 如果new_path：返回new_path 返回无 d ef __str __（self）： return'{}（{}）'。format（self .__ class __.__ name__，dict（self._graph））

我将其作为读者的练习创建一个 find_shortest_path 和其他方法。 p>

让我们看看这个在行动...

>> >连接= [（'A'，'B'），（'B'，'C'），（'B'，'D'），（'C'，'D'），（'E '，'F'），（'F'，'C'）] >>> g = Graph（connections，directed = True）>>> pprint（g._graph） {'A'：{'B'}，'B'：{'D'，'C'}，'C'：{'D '}，'E'：{'F'}，'F'：{'C'}} >>> g =图（连接）＃无向>>> 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'）>>> 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'）>>> pprint（g._graph） {'B'：{'D'，'C'}，'C'：{'D'，'F'，'B'}，'D'：{'C'，'E'，'B'}，'E'：{'D'，'F'}，'F'：{'E' 'C'}} >>> g.add（'G'，'B'）>>>> 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']

How can one neatly represent a graph in Python? (Starting from scratch i.e. no libraries!)What data structure (e.g. dicts/tuples/dict(tuples)) will be fast but also memory efficient?One must be able to do various graph operations on it. As pointed out, the various graph representations might help. How does one go about implementing them in Python?As for the libraries, this question has quite good answers.

Thanks!

解决方案

Even though this is a somewhat old question, I thought I'd give a practical answer for anyone stumbling across this.

Let's say you get your input data for your connections as a list of tuples like so:

[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]

The data structure I've found to be most useful and efficient for graphs in Python is a dict of sets. This will be the underlying structure for our Graph class. You also have to know if these connections are arcs (directed, connect one way) or edges (undirected, connect both ways). We'll handle that by adding a directed parameter to the Graph.__init__ method. We'll also add some other helpful methods.

from collections import defaultdict class 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.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))

I'll leave it as an "exercise for the reader" to create a find_shortest_path and other methods.

Let's see this in action though...

>>> connections = [('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')] >>> g = Graph(connections, directed=True) >>> pprint(g._graph) {'A': {'B'}, 'B': {'D', 'C'}, 'C': {'D'}, 'E': {'F'}, 'F': {'C'}} >>> g = Graph(connections) # undirected >>> 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') >>> 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') >>> pprint(g._graph) {'B': {'D', 'C'}, 'C': {'D', 'F', 'B'}, 'D': {'C', 'E', 'B'}, 'E': {'D', 'F'}, 'F': {'E', 'C'}} >>> g.add('G', 'B') >>> 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']