一种高效的数据结构用于表示图

Question

我需要实现一个有向图（digraph），它允许有多条弧（multigraph），就像链接中的图片一样。该图必须经过优化以处理大量的节点，但是很少有两个节点之间的边缘。该图必须经常更新，并且必须支持高效的路径搜索。哪种数据结构可以在所用空间和查询时间之间取得平衡呢？语言为标准C（仅libc）。 图例

- roger21

---

“频繁更新”是什么意思？指的是边缘更改还是节点更改，例如添加或删除节点？ - Yastanub

什么是“路径搜索”？ - Paul Ogilvie

这意味着节点和边都可以被添加。边可以被删除或添加。 - roger21

路径搜索是指我必须搜索与特定感兴趣节点相关联的节点。 - roger21

Answer 1

假设您有NODE_COUNT个节点。您创建一个长度为NODE_COUNT的向量GRAPH。在条目X中，您有一个大小可变的数组（动态分配）。每个条目看起来像GRAPH [X] = [A1，A2，A3]，表示边缘{（X，A1），（X，A2），（X，A3）}。

如果需要搜索某些边缘，使用二叉搜索树也很方便在条目GRAPH [X]上。如果每个节点有超过6个边缘，则可以考虑这种可能性，而不是在位置GRAPH [X]上使用非有序数组。

由于图具有许多节点和少量边缘，因此不应使用矩阵。

如果您有数百万或数十亿个节点，则问题不同，您应该考虑使用BDDs。这是另一个主题，在此线程中我不会详细介绍。想法是将图表示为表示图的集合的特征函数。

- alinsoar

---

你的答案应该提到这种数据结构的名称：它是邻接表。对于经常更新的稀疏图，它确实是一个很好的表示方式，正如OP所要求的那样。 - Konrad Rudolph

@KonradRudolph 是的，GRAPH[X] 可以是邻接表，或者如果他需要更快的查找，可以是二叉搜索树，或者他可以使用有序数组进行对数时间搜索边缘 -- 他可以根据每个节点的平均边数和他需要在图上执行的操作类型选择其中之一。 - alinsoar

@KonradRudolph ... 或者，他可以选择任何东西来代表一个集合 -- 例如，哥德尔数或中国剩余定理可以代表集合（尽管它们只在节点的索引不大时才实用），https://math.stackexchange.com/questions/113142/using-g%C3%B6del-numbering-to-represent-sets-of-real-numbers - alinsoar

Answer 2

你可以使用邻接矩阵。它本质上是一个显示邻接列表的二维数组。

这里有一个例子。我相信它们非常快，确定图中是否存在边缘需要Θ(1)时间。

如果“频繁更新”指的是更新边缘，那么这将是很好的选择，因为更新值只需花费恒定的时间。(例如，添加edge(3,2)只需在矩阵中增加3,2处的值)

对于确定最短路径，Dijkstra算法是您的最佳选择。

- Gpsy

---

@PaulOgilvie 取决于 OP 所说的“频繁更新”的含义。如果他指的是频繁添加和删除节点，则不行。如果他指的是频繁添加和删除边缘，则可以。 - Yastanub

请注意，这可能会引发问题：“如何在C中实现邻接矩阵？”如果您建议使用2D数组，则对于“许多节点但很少的边缘”，它将是一个相当稀疏的矩阵，并且“有效路径搜索”可能会很棘手。 - Bob__

邻接矩阵不满足"多重弧"要求。 - hager

如果那些数字实际上是权重，那么您是正确的，我将这些数字解释为每个权重的标签，因为它们按1-5进行编号，就好像它们在为边缘编号。 - Gpsy

@Gpsy 现在我明白了 - 你可能是对的，认为那些是标签，我从来没有花时间去读这些数字，仔细一看，它们似乎是标签。 - hager