图数据结构介绍 | Baeldung中文网

1. 概述

图是一种重要的数据结构，理解图在内存中是如何存储的是非常重要的。

在本教程中，我们将解释和比较三种主要的图数据结构，并展示它们的优缺点。

2. 问题定义

在图论中，我们将节点称为顶点 (V) ，将节点之间的连接称为边 (E) 。在处理图存储数据结构时，我们主要基于空间和时间复杂度进行比较。

2.1. 复杂度

对于图存储数据结构，我们通常关注以下几种复杂度：

空间复杂度：存储图所需的大致内存量
时间复杂度
1. 连接检查复杂度：确定两个不同节点是否相邻所需的大致时间
2. 邻居查找复杂度：找到某个目标节点的所有相邻节点所需的大致时间

如果两个不同的节点之间有一条边连接，我们称它们为"相邻节点"。

2.2. 图的类型

理解图通常基于两个因素来定义是很重要的。

第一个因素是图是否是加权的。 在图论中，有时我们只关心两个节点是否连接，而其他时候，我们还关心从节点到节点移动的代价。

在本文中，我们将展示每种数据结构在这两种情况下需要进行的更新。

第二个因素是图是否是有向的。 如果从到有一条边，并且我们只能从节点移动到节点，那么这个图就是有向的。而在无向图中，节点和之间的边意味着我们可以从节点移动到节点，反之亦然。

我们总是可以通过将和之间的每条边分成两条边来将任何无向图转换为有向图。因此，在本文中，我们将讨论有向图，因为它们是更一般的情况。

3. 图数据结构

图在内存中的表示方式，主要有3种

3.1. 邻接矩阵

第一种数据结构称为邻接矩阵。顾名思义，邻接矩阵在我们需要快速确定两个节点是否相邻（连接）时非常有用。邻接矩阵是一个大小为 V^2 的布尔数组。

让我们将其命名为，那么我们应该有：

如果从到有直接边，则 $G_{uv} = true$ 。

否则， $G_{uv} = false$ 。

然而，如果处理的是加权图，那么每个单元格 $G_{uv}$ 将是一个数组，包含和之间直接边的权重。

如果和之间没有边，那么 $G_{uv}$ 将包含一个特殊值，表示和之间没有直接连接。通常，我们可以使用一个很大的值，表示直接在 u 和 v 之间移动代价很高，或者是不可能的。

3.2. 邻接表

第二种数据结构是邻接表。在这种数据结构中，我们不需要存储所有不同对和的值。相反，对于每个节点，我们只存储其相邻节点。

为此，我们创建一个大小为的数组。每个单元格将保存一个链表。链表中的每个对象将存储与索引为的节点相连的节点的索引。因此，每个单元格将有一个大小为 N_u 的链表，其中 N_u 对应于与节点相连的节点数量。

换句话说：

$G_{ui}; i \in [1, N_u]$ ，其中 $G_{ui}$ 等于节点的第 i 个邻居。

如果我们处理的是加权图，那么链表中的每个对象将保存两个信息：相邻节点和与之间边的权重。

3.3. 边列表

最后一种数据结构是边列表。从名称可以推断，我们将图中的所有边存储在一个链表中。

让我们将这个列表称为。链表中的每个对象将保存两个信息：节点和节点，表示存在一条连接节点和节点的边。从上面我们可以推断：

$G_{ui}; i \in [1, E]$ $G_{ui}$ 包含图中第 i 条边的信息。

如果图是有加权的，那么每个对象将包含第三条信息，即节点 u 和 v 之间的边的权重。

这种数据结构对于具有大量节点但只有少量边的图特别有用。

4. 复杂度分析

下面表展示了不同数据结构的复杂度。接下来，我们将解释每个复杂度背后的原因：

数据结构	空间复杂度	时间复杂度
数据结构	空间复杂度	Connection Checking	Neighbors Finding
Adjacency Matrix	$O(V^2)$	$O(1)$	$O(V)$
Adjacency List	$O(V+E)$	$O(N_u)$	$O(N_u)$
Edges List	$O(E)$	$O(E)$	$O(E)$

4.1. 空间复杂度

邻接矩阵：由于邻接矩阵存储了一个大小为的数组，因此空间复杂度为，其中是图中顶点的数量。
邻接表：首先，我们存储一个大小为的数组，每个单元格存储图中一个节点的信息。这意味着我们首先需要的空间复杂度来存储一个空数组。接下来，我们考虑所有链表的大小总和。由于我们只在有新边时创建额外的链表对象，所以链表大小的总和等于，其中是图中边的数量。因此，总的空间复杂度为。
边列表：在这种数据结构中，我们只有一个存储图中所有可能边的链表。因此，空间复杂度为。

4.2. 连接检查复杂度

邻接矩阵：使用邻接矩阵检查两个节点和是否相连非常高效。我们只需查看单元格 $G_{uv}$ 的值即可。因此，时间复杂度为。
邻接表：要确定两个节点和是否相连，我们需要遍历存储在中的链表。在最坏的情况下，和之间没有边，我们将进行次迭代。因此，总复杂度为，其中是的邻居数量。
边列表：在边列表的情况下，我们别无选择，只能遍历链表中的所有边，检查是否能找到节点和之间的边。复杂度为，其中是图中边的数量。

4.3. 邻居查找复杂度

邻接矩阵：要找到某个节点的所有邻居节点，我们需要遍历第 u 行的所有单元格，以确定哪些节点与直接相连。换句话说，我们需要检查所有的，其中 $i \in [1, V]$ 。因此，时间复杂度为。
邻接表：快速找到所有邻居节点正是邻接表的设计初衷。由于单元格存储了一个包含所有与相连的节点的链表，我们只需遍历存储在中的链表即可。这种遍历的时间复杂度为，其中表示节点的邻居数量。
边列表：边列表可能不是快速找到所有邻居节点的最佳解决方案。我们需要遍历链表中存储的所有对象，并检查存储的节点是否为和。因此，时间复杂度为，其中是图中边的数量。

5. 优缺点

邻接矩阵在需要快速检查两个节点之间是否有直接边时很有用。然而，其主要缺点是内存占用较大。邻接矩阵在图的节点数量不太大的情况下最为有效。此外，当图几乎是完全图（每个节点几乎与所有其他节点相连）时，使用邻接矩阵可能是一个不错的选择。

另一方面，邻接表在需要频繁访问某个节点 u 的所有邻居时是一个很好的选择。在这种情况下，我们只需遍历所需的节点。邻接表的局限性在于需要检查两个节点是否有直接边时会显现出来。

不过，值得注意的是，我们可以使用邻接表的改进版本。我们可以使用更复杂的数据结构（如集合）来存储所有邻居节点，而不是使用链表。这样可以高效地遍历邻居节点，同时也能以对数时间复杂度检查两个节点是否相连。

边列表是使用最少的数据结构。主要在节点数量巨大无法存储在内存中，但边数较少的情况下使用边列表。在这种情况下，我们别无选择，只能使用边列表。因此，边列表的唯一优势是其较低的内存空间复杂度。

6. 总结

在本文中，我们介绍了三种主要的图存储数据结构。

接着，我们讨论了大多数图算法执行的主要操作的空间和时间复杂度。

最后，我们探讨了每种数据结构在空间和时间复杂度方面的优缺点，以及何时使用每种数据结构。

Persistence

REST

Security