algorithm - Dijkstra 将图形存储在文本文件中

Question

我想知道，在您实现 Dijkstra 算法时，将图形存储在文本文件中的最有效方法是什么？ (邻接矩阵，关联矩阵？等等)

Answer 1

在一般情况下，一个好的方法是存储所有边的列表。它占用 O(E) 空间:我们在每条边上存储两个端点。将其存储在磁盘上就足够了。

要使用这样的列表，它通常作为 V 邻接列表存储在内存中，每个顶点一个。如果图形是无向的，这将复制每条边(u->v 和 v->u)。然而，图算法的一个常见操作是遍历给定顶点的所有边。通过为每个顶点存储一个邻接列表，我们可以在 O(number of neighbors) 中做到这一点，这是最好的。

邻接矩阵占用 O(V^2) 空间，这对于密集图可能很好，但在一般情况下比 O(E) 差。

关联矩阵占用 O(VE) 空间，并且效率不高，除非您的图表在某种程度上非常特殊才能做到这一点。

Dijkstra 算法最快的实现需要 O(E log V) 时间，因此 O(E) 内存通常没问题。