您好！
在这篇文章中，我决定列出计算机科学中用于存储图形的主要数据结构，并且我还将讨论更多这样的结构，它们以某种方式为我“结晶”。
那么，让我们开始吧。 但不是从一开始——我想我们都已经知道图是什么以及它们是什么（有向、无向、加权、未加权、有或没有多个边和循环）。
那么，我们走吧。 我们对于“图存储”的数据结构有哪些选择？
1. 矩阵数据结构
1.1 邻接矩阵。 邻接矩阵是行列标题对应图的顶点数的矩阵，其每个元素a(i,j)的值由顶点之间有无边决定i 和 j（很明显，对于无向图，这样的矩阵将是对称的，或者我们可以同意我们仅存储主对角线上方的所有值）。 对于未加权图，a(i,j)可以通过i到j的边数来设置（如果没有这样的边，则a(i,j)= 0），对于加权图，也可以通过权重来设置上述边缘的（总重量）。
1.2 关联矩阵。 在这种情况下，我们的图也存储在一个表中，通常，行号对应于其顶点的编号，列号对应于预先编号的边。 如果顶点和边相互关联，则在相应的单元格中写入非零值（对于无向图，如果顶点和边关联则写入 1，对于有向图 - 如果边关联则写入“1”）从顶点“退出”，如果“包含”在其中，则为“-1”（这很容易记住，因为“减号”似乎也“包含”在数字“-1”中））。 对于加权图，您可以指定边的总权重，而不是 1 和 -1。
2. 枚举数据结构
2.1 邻接表。 嗯，这里一切似乎都很简单。 一般来说，图的每个顶点都可以与任何枚举结构（列表、向量、数组……）相关联，该结构将存储与给定顶点相邻的所有顶点的编号。 对于有向图，我们将仅将那些与特征顶点有“有向”边的顶点添加到这样的列表中。 对于加权图，实现会更加复杂。
2.2 肋骨列表。 相当流行的数据结构。 正如 Captain Obviousness 告诉我们的，边列表实际上是图的边列表，每条边都由起始顶点、结束顶点指定（对于无向图，这里的顺序并不重要，尽管为了统一，您可以使用各种规则，例如，按递增顺序指定顶点）和权重（仅适用于加权图）。
您可以更详细地查看上面列出的矩阵列表（并带有插图），例如， .
2.3 邻接数组。 不是最常见的结构。 从本质上讲，它是将邻接表“打包”到一个枚举结构（数组、向量）中的一种形式。 该数组的前 n 个（根据图的顶点数）元素包含同一数组的起始索引，从该索引开始，与给定数组相邻的所有顶点都写入一行。
在这里我找到了最容易理解的（对我自己来说）解释：
3. 邻接向量和关联邻接数组
事实证明，这些行的作者不是专业程序员，而是定期处理图形，最常处理边列表。 事实上，如果图有多个环和边，那就很方便了。 因此，在开发经典的边列表时，我建议关注它们的“开发/分支/修改/变异”，即：邻接向量和关联邻接数组。
3.1 邻接向量
情况 (a1)：未加权图
我们将未加权图的邻接向量称为偶数个整数的有序集合（a[2i], a[2i+1],...，其中 i 编号为 c 0），其中每对数字是a[2i]，a[2i+1]分别指定顶点a[2i]和a[2i+1]之间的图边。
此记录格式不包含有关图是否有向的信息（两个选项都可以）。 当使用有向图格式时，边被认为是从 a[2i] 指向 a[2i+1]。 这里和下面：对于无向图，如果需要，可以应用记录顶点顺序的要求（例如，分配给它的数字值较小的顶点在前）。
在 C++ 中，建议使用 std::vector 指定邻接向量，因此得名该数据结构。
情况（a2）：未加权图，边权重为整数
与情况 (a1) 类比，我们将具有整数边权重的加权图的邻接向量称为数字 (a[3i], a[3i+1], a[3i+2], ...，其中 i 编号为 c 0)，其中数字 a[3i]、a[3i+1]、a[3i+2] 的每个“三元组”指定编号为 a[3i] 的顶点之间的图的一条边和a[3i+1]，a[3i+2]的值是这条边的权重。 这样的图也可以是有向的，也可以是无向的。
情况 (b)：未加权图，非整数边权重
由于不可能将异构元素存储在一个数组（向量）中，因此例如可以采用以下实现。 图存储在一对向量中，其中第一个向量是图的邻接向量，没有指定权重，第二个向量包含相应的权重（C++ 的可能实现：std::pair ）。 因此，对于由第一向量的索引 2i、2i+1 下的一对顶点定义的边，权重将等于第二向量的索引 i 下的元素。
那么，为什么这是必要的呢？
好吧，这些行的作者发现它对于解决许多问题非常有用。 那么，从形式上来看，会有以下几个优点：
- 与任何其他“枚举”结构一样，邻接向量非常紧凑，比邻接矩阵（对于稀疏图）占用更少的内存，并且相对容易实现。
- 图的顶点原则上也可以用负数来标记。 如果需要这样的“变态”怎么办？
- 图可以包含多个边和多个循环，具有不同的权重（正、负、甚至零）。 这里没有任何限制。
- 您还可以为边指定不同的属性 - 但有关更多信息，请参阅第 4 节。
但必须承认，这份“清单”并不意味着快速进入边缘。 在这里，关联邻接数组可以发挥作用，这将在下面讨论。
3.2 关联邻接数组
因此，如果访问特定边、其权重和其他属性对我们来说至关重要，并且内存要求不允许我们使用邻接矩阵，那么让我们考虑如何更改邻接向量来解决这个问题。 因此，关键是图的一条边，它可以指定为一对有序整数。 这看起来像什么？ 它不是关联数组中的键吗？ 如果是这样，我们为什么不实施它呢？ 让我们有一个关联数组，其中每个键（一对有序的整数）将与一个值（指定边权重的整数或实数）关联。 在C++中，建议基于std::map容器（std::map 、 int> 或 std::map 、 double>) 或 std::multimap（如果需要多个边）。 好吧，我们有一个存储图的结构，它比“矩阵”结构占用更少的内存，可以定义具有多个循环和边的图，甚至对顶点数的非负性没有严格的要求（我不知道谁需要这个，但仍然）。
4. 数据结构已满，但缺少一些东西
确实如此：在解决许多问题时，我们可能需要为图的边分配一些特征，并相应地存储它们。 如果可以明确地将这些特征减少为整数，则可以使用邻接向量和关联邻接数组的扩展版本来存储此类“具有附加特征的图”。
因此，让我们有一个未加权的图，对于它的每条边，有必要存储例如 2 个由整数指定的附加特征。 在这种情况下，可以将其邻接向量定义为不是“对”的有序集合，而是整数“四重奏”的有序集合（a[2i]、a[2i+1]、a[2i+2]、a [2i+3]…) ，其中 a[2i+2] 和 a[2i+3] 将确定相应边的特征。 对于具有整数边权重的图，顺序通常相似（唯一的区别是属性将遵循边的权重，并由元素 a[2i+3] 和 a[2i+4] 指定，并且边本身将被指定为 4 个有序数，而不是 5 个）。 对于具有非整数边权重的图，可以将特征写入其未加权的组件中。
当对具有整数边权重的图使用关联邻接数组时，可以指定一个值，而不是单个数字，而是一个数字数组（向量），该数组（向量）除了指定边的权重外，还指定所有其他必要的值特征。 同时，对于非整数权重的情况，一个不便之处是需要指定一个带有浮点数的符号（是的，这是一个不便之处，但是如果没有那么多这样的符号，并且如果你不这样做的话）不要把它们设置得太“棘手”双倍，那么可能就没什么了）。 这意味着在 C++ 中扩展关联邻接数组可以定义如下： std::map 、 std::vector> 或 std::map ，std::vector，其中“键值向量”中的第一个值将是边的权重，然后是其特征的数字名称。
参考文献：
关于一般图和算法：
1. 托马斯·H·科门、查尔斯·一世·莱瑟森、罗纳德·L·里维斯特、克利福德·斯坦因。 算法：构造和分析，第二版：Trans。 源自英语– M.：威廉姆斯出版社，2 年。
2. 赫拉里·弗兰克。 图论。 M.：米尔，1973 年。
作者关于这些相同向量和邻接关联数组的报告：
3. 切尔努霍夫 S.A. 邻接向量和关联邻接数组作为表示和存储图的方式/SA Chernouhov。 邻接向量和邻接图作为数据结构来表示图 // 国际科学与实践会议文章集“实施创新发展成果的问题及其解决方法”（萨拉托夫，14.09.2019 年 2019 月 65 日）。 – Sterlitamak：AMI，69 年，第 XNUMX 页XNUMX-XNUMX
有关该主题的有用在线资源：
4.
5.
来源： habr.com