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

Question

如何在Python中整洁地表示图表？（从头开始即没有使用任何库！）
哪种数据结构（例如字典/元组/字典（元组））既快速又内存高效？
必须能够对其进行各种图表操作。

正如指出的那样，各种图表表示可能会有所帮助。如何在Python中实现它们？

至于使用库的问题，这个问题给出了相当好的答案。

- shad0w_wa1k3r

---

已经有很多库可供使用了：http://graph-tool.skewed.de/performance，https://code.google.com/p/python-graph/，http://networkx.github.io/ - Kassym Dorsel

要实现一个图形，请查看维基百科文章，其中列出了常见的实现方式以及它们在内存和速度方面的效率：http://en.wikipedia.org/wiki/Graph_(abstract_data_type)#Representations - Kassym Dorsel

你可以尝试访问GitHub.com/thePastor/pangaia。它需要进行一些重写，以使用标准库的defaultdict（该代码编写时还未发布）。它使用递归数据结构使其比其他实现更加优雅。 - theDoctor

对于有向图，这篇来自python.org的文章建议使用dict和list的组合。基本上是像这样的 {<parent>: [<child>, ...], ...}。 - djvg

你可以使用字典作为邻接表来实现，其中键是节点，值是每个键的相邻节点列表。 - Shahrukh khan

Answer 1

虽然这是一个有点老的问题，但我认为我可以为任何偶然遇到此问题的人提供一个实用的答案。

假设你获得了一个连接输入数据的元组列表，就像这样：

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

在Python中，我发现用字典集合来表示图最有用和高效。这将是我们的Graph类的基本结构。您还需要知道这些连接是弧（有向，单向连接）还是边缘（无向，双向连接）。我们将通过在Graph.__init__方法中添加一个directed参数来处理这个问题。我们还会添加一些其他有用的方法。

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))

我会将其留作"读者练习"，以创建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']

- mVChr

---

尽管这个问题非常古老，但我认为这正是当时我所期望的答案类型。这个例子真的有助于解释如何进行实现，同时保持它简单易懂。虽然可以在不同的开源库中找到实现，但解释可能无法与之相媲美。谢谢！ - shad0w_wa1k3r

需要进行什么样的修改才能给边添加权重？ - pshirishreddy

很有趣的问题！我从未考虑过这一点，但我的直觉是使用 heapq 库来对元组列表进行堆排序，而不是使用集合。例如，图可以是字典堆的形式：_graph = {'A': heapify([(0.3, 'D'), (0.5, 'B'), (0.75, 'A'), (0.9, 'C')])}（注意：实际上不会像这样使用 heapify，请阅读该库的帮助），然后您可以使用 heapq 函数插入和获取加权边。 - mVChr

@mVChr，那就意味着需要log时间访问。但是如何扩展您用于映射nodeID和weight的字典？ - orezvani

不错！函数被递归调用。这似乎是深度优先搜索，因为它不断扩展节点。对于最短路径，我们可以比较路径的长度，并在最后仅返回最短路径。 - Jwalant Bhatt

嗨，把这个数据结构称为邻接表实现是否正确？ - Ghos3t

Answer 2

NetworkX 是一个非常棒的 Python 图形库。你会很难找到它没有完成的需求。

而且它是开源的，所以你可以查看它们如何实现自己的算法。你还可以添加其他算法。

https://github.com/networkx/networkx/tree/master/networkx/algorithms

- jterrace

---

这就是为什么NetworkX是一个很棒的资源。它是开源的，所以你可以看到他们是如何实现它们的算法的。你还可以添加额外的算法。 - jterrace

大约有2000行代码是关于graph.py --> class Graph的。我只想看看他们如何使用__iter__。 - T.Woody

Answer 3

首先，选择经典的列表(list)与矩阵(matrix)表示取决于目的（即您要用表示做什么）。已知的问题和算法与选择有关。抽象表示的选择在一定程度上决定了它应该如何实现。

其次，问题是顶点和边是否只以存在的方式表示，还是它们携带一些额外信息。

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

Python列表是作为引用的动态数组实现的，Python元组是作为具有恒定内容的引用静态数组实现的（引用的值不能更改）。由于这样，它们可以很容易地进行索引。这种方式，列表也可以用于矩阵的实现。

另一种表示矩阵的方法是由标准模块array实现的数组 - 与存储的类型相比更受限制，具有同类值。元素直接存储值。(列表存储指向值对象的引用)。这样，它更节省内存，访问值也更快。

有时候，您甚至可能会发现有用的是更受限制的表示，如bytearray。

- pepr

Answer 4

有两个优秀的图形库NetworkX和igraph。你可以在GitHub上找到这两个库的源代码，可以看到函数是如何编写的。但我更喜欢NetworkX，因为它易于理解。
查看它们的代码以了解如何创建函数。你将获得多个想法，然后可以选择使用数据结构来制作图形。

- Vineet Jain