c - 用于表示图的高效数据结构

Question

我必须实现一个有向图(digraph)，它允许有多个弧(multigraph)，就像链接的图像一样。该图必须进行优化以处理大量节点，但其中两个节点之间的边缘很少。该图必须经常更新，并且必须支持有效的路径搜索。哪个是在使用空间和查询时间之间折衷的有效数据结构？语言是标准 C(仅 libc)。

graph example

Answer 1

假设你有 NODE_COUNT节点。您创建了一个 vector GRAPH长度NODE_COUNT .在条目 X你有一个可变大小的数组(动态分配)。每个条目看起来像 GRAPH[X]=[A1, A2, A3]表示边缘 { (X,A1), (X,A2), (X,A3) } .

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

因为图形有很多节点和很少的边，所以你不应该使用矩阵。

如果您有数百万或数十亿个节点，问题就不同了，您应该考虑使用 BDDs .这是另一个话题，我不会在此线程中详细输入。这个想法是，图可以表示为表示该图的集合的特征函数。