在内存中存储图形的三种方法,优缺点

分析这些问题的一种方法是根据内存和时间复杂性(这取决于您希望如何访问图形)。

• 这种方法的内存复杂度是O(n),因为对象和节点的数量一样多。所需的指针(到节点)的数目最多为O(n^2),因为每个节点对象最多可以包含n个节点的指针。
• 该数据结构的时间复杂度为O(n),用于访问任何给定的节点。

• 对于矩阵,这将是O(n^2)的内存复杂度。

根据在图上运行的算法以及有多少节点,您必须选择合适的表示。

还有几件事需要考虑:

2. 与无向图相比,对象/指针模型在有向图中工作得更好,因为指针需要成对维护,这可能会变得不同步。

正如一些人所指出的,objects和pointers方法存在搜索困难的问题,但是对于构建二叉搜索树(其中有很多额外的结构)这样的事情来说是非常自然的。

我个人喜欢邻接矩阵,因为它们使用代数图论中的工具,使各种问题变得容易得多(例如,邻接矩阵的第k次方给出了从顶点i到顶点j的长度为k的路径数。在取第k次幂之前添加一个单位矩阵,以获得长度的路径数<=k。取拉普拉斯级数的n-1次方得到生成树的个数。。。以此类推。)

但是每个人都说邻接矩阵是内存昂贵的!它们只对了一半:当你的图几乎没有边时,你可以使用稀疏矩阵来解决这个问题。稀疏矩阵数据结构只需要保持一个邻接列表就可以了,但是仍然有标准矩阵操作的全部可用范围,使您可以两全其美。

我认为你的第一个例子是有点模棱两可的节点作为对象,边作为指针。您可以通过只存储指向某个根节点的指针来跟踪这些节点,在这种情况下,访问给定的节点可能效率低下(假设您想要节点4如果没有提供节点对象,您可能需要搜索它)。在这种情况下,还将丢失无法从根节点访问的部分图形。我认为这就是F64Rainbow假设的情况,他说访问给定节点的时间复杂度是O(n)。

否则,还可以保持一个数组(或hashmap)中充满指向每个节点的指针。这允许O(1)访问给定的节点,但会稍微增加内存使用量。如果n是节点数,e是边数,则该方法的空间复杂度为O(n+e)。

矩阵方法的空间复杂度将沿着O(n^2)线(假设边是单向的)。如果你的图是稀疏的,那么你的矩阵中会有很多空单元格。但是如果你的图是完全连通的(e=n^2),这与第一种方法相比是有利的。正如RG所说,如果将矩阵分配为一块内存,那么使用这种方法也可能会减少缓存未命中,这可以使跟踪图形周围的许多边的速度更快。

第三种方法在大多数情况下可能是最节省空间的O(e),但会使查找给定节点的所有边成为O(e)的一项繁重工作。我想不出这在什么情况下会很有用。

看一看 comparison table 在维基百科上。它很好地理解了何时使用每种图形表示法。

还有另一种选择:节点作为对象,边也作为对象,每条边同时位于两个双链表中:来自同一节点的所有边的列表和进入同一节点的所有边的列表。

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

内存开销很大(每个节点2个指针,每条边6个指针),但是

• O(1)节点插入
• O(1)边插入(给定指向“from”和“to”节点的指针)
• O(1)删除边(给定指针)
• O(deg(n))节点删除(给定指针)
• O(deg(n))查找节点的邻居

该结构还可以表示一个相当通用的图:带循环的定向多重图(即,在相同的两个节点之间可以有多个不同的边,包括多个不同的循环-从x到x的边)。

对这种方法有更详细的解释 here .

如果图是稀疏的,那么对象/指针方法似乎效率更高。在数据结构中保持对象/指针以将它们引导到单个内存块中也可能是一个很好的计划,或者任何其他使它们保持在一起的方法。

邻接列表——仅仅是一个连接节点的列表——似乎是迄今为止最有效的内存,但也可能是最慢的。

反转有向图是 容易的 使用矩阵表示法和邻接列表很容易,但使用对象/指针表示法就不太好了。