在Python中表示graphics（数据结构）
在Python中如何巧妙地表示graphics ？ （从头开始，即没有图书馆！）
什么数据结构（例如字典/元组/字典（元组））将是快速的，但也是有效的内存？
一个人必须能够对其进行各种图表操作 。
正如指出的那样，各种图表可能有所帮助。 如何在Python中实现它们？
至于图书馆， 这个问题有相当好的答案。
尽pipe这是一个有些古老的问题，但我想我会给出一个实际的答案。
假设你将你的连接的input数据作为一个元组列表，如下所示：
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')] 我发现数据结构对于Python中的graphics来说是最有用和最有效率的，这是一组字典 。 这将是我们Graph类的底层结构。 你也必须知道这些连接是弧（直接，连接）还是边（无向，连接）。 我们将通过向Graph.__init__方法添加一个directed参数来处理这个问题。 我们还会添加一些其他有用的方法。
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))
我将把它作为“读者的练习”来创build一个find_shortest_path和其他方法。
让我们看看这个在行动虽然…
>>> 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']
NetworkX是一个很棒的Pythongraphics库。 你会很难find你所需要的东西，而现在还没有。
首先，经典列表与matrix表示的select取决于目的（你想用表示做什么）。 众所周知的问题和algorithm与select有关。 抽象表示types的select决定了如何实现。
其次，问题是顶点和边缘是否应该仅以存在的方式expression，或者是否携带一些额外的信息。
从Python内置的数据types的angular度来看，其他地方包含的任何值都表示为对目标对象的（隐藏）引用。 如果它是一个variables（即名为引用），那么名称和引用总是存储在（内部）字典中。 如果你不需要名称，那么引用可以存储在你自己的容器中 – 这里可能总是用Python 列表作为抽象。
Python列表被实现为一个dynamic的引用数组，Python元组被实现为具有常量内容的引用的静态数组（引用的值不能被改变）。 因为它们可以很容易地索引。 这样，列表也可以用于matrix的实现。
表示matrix的另一种方式是由标准模块array实现的array – 关于存储types，均匀值，更多地受到限制。 元素直接存储值。 （该列表将存储对值对象的引用）。 这样，它的内存效率更高，并且访问值更快。
有时候，你可能会发现像bytearray这样更有限的表示。
有两个优秀的graphics库NetworkX和igraph 。 你可以在GitHub上find两个库源代码。 你总是可以看到函数的写法。 但是我更喜欢NetworkX，因为它易于理解。
看他们的代码如何做function。 你会得到多个想法，然后select你想要使用数据结构来创build一个图。
