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

Question

有三种方法可以在内存中存储图形:

1. 节点作为对象,边缘作为指针
2. 包含编号节点x和节点y之间的所有边缘权重的矩阵
3. 编号节点之间的边缘列表

我知道如何写这三个,但我不确定我是否已经考虑过每个人的所有优点和缺点.

将这些图存储在内存中的每种方法有哪些优点和缺点？

Answer 1

分析这些的一种方法是在内存和时间复杂度方面(这取决于您希望如何访问图表).

将节点存储为具有彼此指针的对象

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

存储边权重矩阵

• 这将是矩阵的O(n ^ 2)的存储器复杂度.
• 该数据结构的优点是访问任何给定节点的时间复杂度为O(1).

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

Answer 2

还有几件事需要考虑:

1. 通过将权重存储在矩阵中,矩阵模型更容易使其具有加权边的图.对象/指针模型需要在并行数组中存储边权重,这需要与指针数组同步.

2. 对象/指针模型使用有向图比无向图更好地工作,因为指针需要成对维护,这可能变得不同步.

Answer 3

正如一些人所指出的那样,对象和指针方法存在搜索困难,但是对于构建二元搜索树这样的事情非常自然,这里有很多额外的结构.

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

但是每个人都认为邻接矩阵的内存很贵!它们只有一半右:当图形边缘很少时,你可以使用稀疏矩阵来解决这个问题.稀疏矩阵数据结构完全可以保留邻接列表,但仍然具有可用的标准矩阵操作的全部范围,为您提供两全其美的优势.

Answer 4

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

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

矩阵方法的空间复杂度将沿着O(n ^ 2)的线(假设边是单向的).如果图形稀疏,则矩阵中将包含大量空单元格.但是如果你的图形是完全连接的(e = n ^ 2),这与第一种方法相比是有利的.正如RG所说,如果将矩阵分配为一块内存,这种方法可能也会减少缓存未命中次数,这可能会使图形周围的许多边缘更快.

对于大多数情况,第三种方法可能是空间效率最高的 - O(e) - 但是会使找到给定节点的所有边缘成为O(e)家务.我想不出这个非常有用的案例.

Answer 5

好的，如果边没有权重，矩阵可以是二元数组，在这种情况下使用二元运算符可以让事情变得非常非常快。

如果图形稀疏，则对象/指针方法似乎更有效。将对象/指针保存在数据结构中，专门将它们放入单个内存块中也可能是一个很好的计划，或者让它们保持在一起的任何其他方法。

邻接列表 - 只是连接节点的列表 - 似乎是迄今为止内存效率最高的，但也可能是最慢的。

使用矩阵表示法反转有向图很容易，使用邻接表也很容易，但使用对象/指针表示法就不那么容易了。

Answer 6

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

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 的边）。

此处提供了此方法的更详细说明。

Answer 7

看看维基百科上的比较表。它可以很好地理解何时使用图形的每个表示。