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

EN

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

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

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

如果您有数百万或数十亿个节点，那么问题就不同了，您应该考虑使用BDDs。这是另一个话题，我不会在这个帖子中详细介绍。其思想是，图可以表示为表示该图的集合的特征函数。

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

​

下面是一个例子。我相信它们是相当快的，它需要Θ(1)时间来确定图中是否存在边。

如果“频繁更新”指的是更新边，这将是很好的，因为更新其中一个值需要恒定的时间。(即添加边( 3, 2 )将需要恒定的时间，因为您只需将矩阵中3，2处的值递增)

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