如何在Python中巧妙地表示图形？（从头开始，即没有库！）什么数据结构（例如dicts/tuples/dict(tuples)）会很快而且内存效率很高？必须能够对其进行各种图形操作。
正如所指出的，各种图形表示可能会有所帮助。如何在 Python 中实现它们？至于图书馆，这个问题有很好的答案。
问问题
118845 次
4 回答
183
尽管这是一个有点老的问题，但我想我会为任何遇到这个问题的人提供一个实用的答案。
假设您将连接的输入数据作为元组列表获取，如下所示：
[('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]
我发现对 Python 中的图形最有用和最有效的数据结构是dict of sets。这将是我们Graph类的底层结构。您还必须知道这些连接是弧（有向，单向连接）还是边（无向，双向连接）。我们将通过向该方法添加一个directed参数来处理它Graph.__init__。我们还将添加一些其他有用的方法。
import pprint
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.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))
我将把它作为“读者练习”来创建 afind_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']
于 2015-06-10T04:16:19.560 回答
48
NetworkX是一个很棒的 Python 图形库。你会很难找到你需要但它还没有做的东西。
它是开源的，所以你可以看到他们是如何实现他们的算法的。您还可以添加其他算法。
https://github.com/networkx/networkx/tree/master/networkx/algorithms
于 2013-10-20T00:15:07.353 回答
8
首先，经典列表与矩阵表示的选择取决于目的（取决于您想对表示做什么）。众所周知的问题和算法都与选择有关。抽象表示类型的选择决定了它应该如何实现。
其次，问题是顶点和边是否应该仅根据存在来表达，或者它们是否携带一些额外的信息。
从 Python 内置数据类型的角度来看，其他地方包含的任何值都表示为对目标对象的（隐藏）引用。如果它是一个变量（即命名引用），那么名称和引用总是存储在（内部）字典中。如果您不需要名称，则可以将引用存储在您自己的容器中——这里可能Python 列表将始终用于列表作为抽象。
Python list 实现为动态引用数组，Python tuple 实现为具有常量内容的静态引用数组（引用的值不能更改）。因此，它们可以很容易地被索引。这样，列表也可以用于矩阵的实现。
表示矩阵的另一种方法是标准模块实现的数组array——在存储类型和同类值方面受到更多限制。元素直接存储值。（该列表存储对值对象的引用）。这样，它的内存效率更高，对值的访问也更快。
有时，您可能会发现有用的甚至更受限制的表示形式，例如bytearray.
于 2013-10-24T20:31:20.583 回答