大家好
在本说明中，我决定列出计算机科学中用于存储图形的主要数据结构，并讨论由我以某种方式实现的其他一些结构。
因此，让我们开始吧。 但不是一开始就-我认为图是什么以及它们是什么（有向，无向，加权，不加权，有多个边和循环或没有它们），我们都已经知道。
所以走吧 我们拥有用于“图形存储”的数据结构的选项是什么。
1.矩阵数据结构
1.1
邻接矩阵 邻接矩阵是这样的矩阵，其中行标题和列标题对应于图的顶点数，并且其每个元素a（i，j）的值由顶点i和j之间是否存在边来确定（很显然，这种无向图的矩阵将会是对称的，或者您可以同意我们仅将所有值存储在主对角线上方）。 对于未加权图，可以通过从i到j的边数来指定（i，j）（如果没有这样的边，则a（i，j）= 0）;对于加权图，还可以通过上述边的权重（总权重）来指定。
1.2
发生率矩阵。 在这种情况下，我们的图也存储在一个表中，其中，行号通常对应于其顶点的编号，而列号对应于预先编号的边。 如果顶点和边相互入射，则在相应的像元中写入一个非零值（对于无向图，在顶点和边发生入射的情况下为1；如果定向图的边“离开”顶点，则为1；如果是边，则为“ -1”。它“输入”（它很容易记住，因为减号似乎也“包含”在数字“ -1”中））。 同样，对于加权图，可以指定边的总权重，而不是1和-1。
2.枚举数据结构
2.1
邻接表 好吧，一切似乎都很简单。 通常，图的每个顶点都可以与任何枚举结构（列表，向量，数组等）相关联，其中将存储与该枚举相邻的所有顶点的数量。 对于有向图，我们将仅列出从属性顶点开始具有“有向”边的顶点。 对于加权图，实现会更加复杂。
2.2
肋骨列表。 相当流行的数据结构。 正如Captain Evidence告诉我们的那样，边列表实际上是图的边列表，每个边都由初始顶点，结束顶点定义（对于无向图，这里的顺序并不重要，尽管可以使用不同的规则进行统一，例如，按顺序指定顶点递增）和权重（仅适用于加权图）。
关于上面列出的矩阵列表，您可以查看（例如，
在此处 ）更详细的信息。
2.3
邻接数组。 不是最常见的结构。 它的核心是一种将邻接表“打包”成一个枚举结构（数组，向量）的形式。 这样的数组的前n个（按图形顶点的数量）包含相同数组的起始索引，从该索引开始，将与其相邻的所有顶点连续写入其中。
在这里，我找到了最容易理解的解释：
ejuo.livejournal.com/4518.html3.邻接向量和关联邻接数组
碰巧的是，这些行的作者不是专业的程序员，而是定期处理图形，而大多数情况下是处理边列表。 确实，如果图形具有多个回路和边线，将很方便。 现在，在开发经典边列表时，我建议注意它们的“开发/分支/修饰/突变”，即：邻接向量和邻接数组。
3.1邻接向量案例（A1）：未加权计数我们将未加权图的邻接向量称为偶数个整数的有序集合（a [2i]，[2i + 1]，...，其中i编号为c 0），其中每对数字a [2i]，[2i +1]分别定义了顶点a [2i]和[2i + 1]之间的图的边缘。
此记录格式不包含有关图形是否定向的信息（两个选项都是可能的）。 当使用有向图格式时，假定边从[2i]指向[2i +1]。 在下文中：对于无向图，如有必要，可以应用记录顶点顺序的要求（例如，使分配给它的数字较小的那个顶点首先出现）。
在C ++中，建议使用std :: vector指定邻接向量，并从中选择此数据结构的名称。
情况（a2）：未加权图，整数边缘权重类似于情况（a1），我们将具有整数边缘权重的加权图的邻接向量称为数字的有序集合（动态数组）（a [3i]，[3i + 1]，[3i + 2]，...，其中i的编号为c 0），其中数字a [3i]，[3i + 1]，[3i + 2]的每个“三元组”分别定义了数字a [3i]和[3i + 1]下顶点之间的图的边缘，并且[3i + 2]的值是该边的权重。 这样的图也可以是有方向的或没有方向的。
情况（b）：未加权图，非整数边缘权重由于异质元素不能存储在一个数组（向量）中，因此以下实现是可能的。 该图存储在一对向量中，其中第一个向量是图的邻接向量，没有指示权重，第二个向量包含相应的权重（C ++的可能实现是：std :: pair <std :: vector，std :: vector>）。 因此，对于在第一矢量的索引2i，2i +1下由一对顶点定义的边，权重将等于在第二矢量的索引i下的元素。
好吧，为什么这是必要的？好了，对于解决这些问题的这些行的作者来说，这似乎很有用。 好吧，从正式的角度来看，会有这样的优势：
- 像任何其他“枚举”结构一样，邻接向量足够紧凑，与邻接矩阵（对于稀疏图）相比占用更少的内存，实现起来相对简单。
- 原则上，图的顶点可以标记为负数。 突然，也需要这种“变态”。
- 图可以包含具有不同权重（正，负，甚至零）的多个边和多个循环。 这里没有限制。
- 可以为肋骨分配不同的属性-但有关此内容，请参见第4段。
但是，我必须承认，这种“ listot”并不意味着可以快速进入肋骨。 在这里，联合邻接数组急于提供帮助，有关以下内容。
3.2关联邻接数组因此，如果对我们来说访问特定边缘，其权重和其他属性至关重要，并且内存要求不允许使用邻接矩阵，那么请考虑如何更改邻接向量以解决此问题。 因此，关键是图的边缘，可以将其定义为有序的整数对。 看起来像什么？ 它可能是关联数组中的键吗？ 如果是这样，我们为什么不执行呢？ 让我们有一个这样的关联数组，其中每个键（一个有序的整数对）将与一个值（一个指定边缘权重的整数或实数）相关联。 在C ++中，建议在std :: map容器的基础上实现此结构（std :: map <std :: pair <int，int>，int>或std :: map <std :: pair <int，int>，double>） ，如果假定有多个边，则返回std :: multimap。 好了，这里我们有一个用于存储图的结构，它比“矩阵”结构占用更少的内存，可以定义具有多个循环和边的图，甚至对顶点数的非负数也没有严格要求（我不知道谁需要它，但仍然）。
4.数据结构至少“泛滥”，但缺少某些内容
事实是：解决许多问题时，我们可能需要为图的边缘分配一些属性，并相应地进行存储。 如果可以将这些特征明确地简化为整数，则可以使用邻接向量和关联邻接数组的扩展版本来存储“带有附加特征的图形”。
因此，让我们有一个未加权的图，对于它的每个边，有必要存储例如2个由整数指定的其他符号。 在这种情况下，可以将其邻接向量指定为不是整数的“四对”（a [2i]，[2i + 1]，[2i + 2]，[2i + 3]。）的有序集合。 。），其中[2i + 2]和[2i + 3]将确定相应边的特征。 对于具有整数边缘权重的图，其顺序通常是相似的（唯一的区别是符号遵循边缘权重并由元素[2i + 3]和[2i + 4]给出，并且将指定边缘本身不是4，而是5个有序数字）。 对于具有非整数边缘权重的图，可以将属性写入其未加权分量。
当对具有整数边缘权重的图使用关联邻接数组时，可以不指定单个数字，而是指定数字的数组（向量），除了边缘权重以外，还指定所有其他必要的属性。 同时，对于非整数权重的情况，不便之处在于需要指定一个带有浮点数的字符（是的，这是不便之处，但是如果没有那么多这样的符号，并且如果您不将它们设置得太“稀疏”，那么可能就没什么了） 。 因此，在C ++中，可以如下定义扩展的关联邻接数组：std :: map <std :: pair <int，int>，std :: vector>或std :: map <std :: pair <int，int>， std :: vector，“ key-vector-value-by-key”中的第一个值是边缘的权重，然后找到其特征的数字标记。
参考文献：
一般而言，关于图和算法：1. Cormen，Thomas H.，Leiserson，Charles I.，Rivest，Ronald L.，Stein，Clifford。 算法：构造和分析，第二版：Per。 来自英语 -M .：威廉姆斯出版社，2011年。
2. Harari Frank。 图论。 M .：米尔，1973年。
作者关于这些相同向量和邻接数组的报告：3. Chernoukhov S.A. 邻接向量和关联邻接数组作为表示和存储图的方式/ SA Chernouhov。 邻接向量和邻接图作为表示图的数据结构//国际科学和实践会议“实施创新发展成果的问题及其解决方法”的文章集（萨拉托夫，2019年9月14日）。 -斯特里塔玛克（Sterlitamak）：AMI，2019年，第15页。 65-69
关于该主题的有用的互联网资源：4.prog-cpp.ru/数据图5.
ejuo.livejournal.com/4518.html