除了邻接表或邻接矩阵之外，还有其他数据结构来表示图吗？

Question

我正在寻找用于表示图形的不同数据结构，我遇到了 Nvidia CUDA Toolkit，并在 source_indices、destination_offsets 的帮助下找到了表示图形的新方法。

被这种创新的图形表示所吸引，我寻找了其他表示图形的方法。但没有发现任何新东西。

我想知道除了邻接矩阵或列表之外，是否还有其他方式来表示图...

Answer 1

我想知道除了邻接矩阵或列表之外是否还有其他方法来表示图......

邻接列表或邻接矩阵还有其他选择，例如边列表、邻接图或前向星形等。鉴于此图（图片取自此处）：

• 这是邻接矩阵表示：

• 这是邻接表表示：

• 这将是另一种选择，边缘列表：

• 另一个很常见的就是前向明星表示：

如果您进入这个研究领域，您会发现很多方法，主要是针对特定案例的优化，同时考虑以下因素：

• 图大小（节点数）
• 图的密度
• 有向图或无向图
• 静态或动态图
• 图在编译时已知或在运行时构造
• 节点 ID（按顺序标记或不按顺序标记）
• ...

例如，这些优化可以支持在预处理阶段对节点进行重新排序以增加参考局部性。最短路径算法有很多工作，特别是在计算世界地图中的最短路径时。

优化的一个例子是适用于大规模交通网络的动态图结构（打包内存图（PMG） ） 。