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

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.

如何在Python中巧妙地表示图形？ （从头开始，即没有库！）什么数据结构（例如dicts / tuples / dict（元组））将快速但内存效率高？一个人必须能够对其进行各种图形操作。正如所指出的，各种图表表示可能会有所帮助。如何在Python中实现它们？至于图书馆，这个问题有很好的答案。

4 个解决方案

#1

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.

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

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.

我将把它留作“读者练习”来创建一个find_shortest_path和其他方法。

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']

#2

NetworkX is an awesome Python graph library. You'll be hard pressed to find something you need that it doesn't already do.

NetworkX是一个很棒的Python图形库。你很难找到你还没有做过的东西。

#3

First, the choice of classical list vs. matrix representations depends on the purpose (on what do you want to do with the representation). The well-known problems and algorithms are related to the choice. The choice of the abstract representation kind of dictates how it should be implemented.

首先，经典列表与矩阵表示的选择取决于目的（关于表示你想做什么）。众所周知的问题和算法与选择有关。抽象表示的选择决定了它应该如何实现。

Second, the question is whether the vertices and edges should be expressed only in terms of existence, or whether they carry some extra information.

其次，问题是顶点和边缘是否应仅仅根据存在来表达，或者它们是否带有一些额外的信息。

From Python built-in data types point-of-view, any value contained elsewhere is expressed as a (hidden) reference to the target object. If it is a variable (i.e. named reference), then the name and the reference is always stored in (an internal) dictionary. If you do not need names, then the reference can be stored in your own container -- here probably Python list will always be used for the list as abstraction.

从Python内置数据类型的观点来看，其他地方包含的任何值都表示为对目标对象的（隐藏）引用。如果它是变量（即命名引用），则名称和引用始终存储在（内部）字典中。如果您不需要名称，那么引用可以存储在您自己的容器中 - 这里可能Python列表将始终用作列表作为抽象。

Python list is implemented as a dynamic array of references, Python tuple is implemented as static array of references with constant content (the value of references cannot be changed). Because of that they can be easily indexed. This way, the list can be used also for implementation of matrices.

Python列表实现为动态引用数组，Python元组实现为具有常量内容的引用的静态数组（引用的值不能更改）。因此，它们可以很容易地编入索引。这样，该列表也可用于实现矩阵。

Another way to represent matrices are the arrays implemented by the standard module array -- more constrained with respect to the stored type, homogeneous value. The elements store the value directly. (The list stores the references to the value objects instead). This way, it is more memory efficient and also the access to the value is faster.

表示矩阵的另一种方法是由标准模块阵列实现的数组 - 相对于存储类型，均匀值更受限制。元素直接存储值。 （该列表存储对值对象的引用）。这样，它可以提高内存效率，并且对值的访问速度也更快。

Sometimes, you may find useful even more restricted representation like bytearray.

有时，您可能会发现有用的更有限的表示形式，如bytearray。

#4

There are two excellent graph libraries NetworkX and igraph. You can find both library source codes on GitHub. You can always see how the functions are written. But I prefer NetworkX because of its ease to understand.
See their codes how they make the functions. You will get multiples idea and then chose how you want to make a graph using data structures.

有两个优秀的图形库NetworkX和igraph。您可以在GitHub上找到两个库源代码。您始终可以看到函数的编写方式。但我更喜欢NetworkX，因为它易于理解。查看他们的代码如何实现这些功能。您将获得多个想法，然后选择使用数据结构制作图形的方式。