邻接表和邻接矩阵图数据结构的两种核心表示方法及其对比

图的表示：为什么需要邻接表和邻接矩阵？

图是计算机科学中一种非常重要的数据结构，用来表示实体之间的关系。这些实体被称为顶点（Vertex）或节点（Node），它们之间的关系被称为边（Edge）。为了能在计算机程序中处理图，我们需要一种方法来存储这些顶点和边。邻接表和邻接矩阵就是最常用的两种存储图的方式。选择哪种表示方法取决于图的特性（例如顶点数量、边的数量）以及我们需要对图执行的操作。

什么是邻接矩阵？

邻接矩阵是一种用二维数组来表示图的方法。假设一个图有 V 个顶点，编号从 0 到 V-1。一个邻接矩阵就是一个 V x V 的方阵，记为 Adj。

矩阵中的元素 Adj[i][j] 的含义取决于图的类型：

无向图：如果顶点 i 和顶点 j 之间存在一条边，那么 Adj[i][j] 和 Adj[j][i] 通常设置为 1。如果不存在边，则设置为 0。对于带权图，Adj[i][j] 可以存储边的权重，不存在的边可以用 0 或无穷大表示。由于无向图的边是双向的，邻接矩阵是对称的（Adj[i][j] = Adj[j][i]）。
有向图：如果从顶点 i 到顶点 j 存在一条有向边，那么 Adj[i][j] 设置为 1（或权重）。如果不存在从 i 到 j 的边，则设置为 0（或无穷大）。注意，Adj[i][j] != Adj[j][i] 在有向图中是常见的。

如何构建邻接矩阵？

构建一个有 V 个顶点、E 条边的图的邻接矩阵的基本步骤如下：

创建一个大小为 V x V 的二维数组（例如，用一个整数数组或布尔数组）。
将数组中的所有元素初始化为 0（对于非带权图）或代表没有边的值（例如，0 或一个很大的数表示无穷大，对于带权图）。
遍历图中的所有边。对于每条边 (u, v)：
- 如果图是无向图，设置矩阵元素 Adj[u][v] = 1 且 Adj[v][u] = 1（或权重）。
- 如果图是有向图，设置矩阵元素 Adj[u][v] = 1（或权重）。

邻接矩阵如何工作？（常见操作）

使用邻接矩阵执行一些常见图操作的方式如下：

检查是否存在从顶点 i 到顶点 j 的边：只需检查矩阵元素 Adj[i][j] 是否为 1（或非零权重）。这个操作非常快，时间复杂度为 O(1)。
查找顶点 i 的所有邻居：遍历矩阵的第 i 行（对于无向图也可以是第 i 列）。所有 Adj[i][j] 非零的 j 都是顶点 i 的邻居。这个操作需要检查 V 个可能的邻居，时间复杂度为 O(V)。
添加一条从顶点 i 到顶点 j 的边：只需将 Adj[i][j] 设置为 1（或权重）。如果图是无向的，还需要设置 Adj[j][i] = 1。这个操作非常快，时间复杂度为 O(1)。
删除一条从顶点 i 到顶点 j 的边：只需将 Adj[i][j] 设置为 0（或代表没有边的值）。如果图是无向的，还需要设置 Adj[j][i] = 0。这个操作也非常快，时间复杂度为 O(1)。

什么是邻接表？

邻接表是一种用链表或动态数组的数组来表示图的方法。它是一个长度为 V 的数组（或向量），数组的每个索引 i 对应于图中的顶点 i。数组中的每个元素 AdjList[i] 是一个列表（或链表、向量等），存储了所有与顶点 i 直接相连的顶点。

更具体地说：

无向图：AdjList[i] 存储了所有顶点 j，使得顶点 i 和顶点 j 之间存在一条边。如果边 (i, j) 存在，那么 j 会出现在 AdjList[i] 中，i 会出现在 AdjList[j] 中。
有向图：AdjList[i] 存储了所有顶点 j，使得存在一条从顶点 i 到顶点 j 的有向边。即 AdjList[i] 存储的是顶点 i 的所有出邻居。

对于带权图，存储在列表中的元素可以是对或结构体，包含邻居顶点的编号以及与该邻居相连的边的权重。

如何构建邻接表？

构建一个有 V 个顶点、E 条边的图的邻接表的基本步骤如下：

创建一个包含 V 个空列表（或动态数组）的数组（或向量）。
遍历图中的所有边。对于每条边 (u, v)：
- 如果图是无向图，将顶点 v 添加到 AdjList[u] 的列表中，并将顶点 u 添加到 AdjList[v] 的列表中。
- 如果图是有向图，将顶点 v 添加到 AdjList[u] 的列表中。

添加到列表的操作通常是添加到列表的头部或尾部，这通常是高效的。

邻接表如何工作？（常见操作）

使用邻接表执行一些常见图操作的方式如下：

检查是否存在从顶点 i 到顶点 j 的边：需要遍历顶点 i 的邻接列表 AdjList[i]，查找其中是否存在顶点 j。在最坏情况下（j 是 i 的最后一个邻居或不是邻居），需要遍历整个列表。这个操作的时间复杂度取决于顶点 i 的度（即与其相连的边的数量），记为 O(degree(i))。对于有向图，是出度。
查找顶点 i 的所有邻居：只需访问并遍历 AdjList[i] 中的所有元素。这个操作的时间复杂度取决于顶点 i 的度，为 O(degree(i))。
添加一条从顶点 i 到顶点 j 的边：将顶点 j 添加到 AdjList[i] 的列表中。如果图是无向的，还需要将 i 添加到 AdjList[j] 中。如果允许平行边，这通常是 O(1) 操作（例如，添加到链表头部）。如果需要检查是否已存在边以避免平行边，则需要先执行检查操作，时间复杂度变为 O(degree(i))。一般我们考虑不检查平行边的情况，添加为 O(1)。
删除一条从顶点 i 到顶点 j 的边：需要在 AdjList[i] 的列表中找到 j 并将其删除。如果图是无向的，还需要从 AdjList[j] 中删除 i。在列表中查找和删除元素的时间复杂度取决于列表的实现（例如，链表或动态数组）以及元素的位置，通常是 O(degree(i))。

空间开销：邻接矩阵 vs 邻接表

这是邻接表和邻接矩阵之间一个非常重要的区别，直接回答了“多少”空间的问题。

邻接矩阵：需要一个 V x V 的二维数组。无论图中有多少边，都需要 V² 个存储单元来表示顶点之间的所有可能关系。因此，空间复杂度总是 O(V²)。即使图只有很少的边，空间开销也与顶点数量的平方成正比。
邻接表：需要一个包含 V 个列表的数组/向量，以及存储所有边的空间。每个顶点 i 在列表中存储与其相连的邻居。对于每条无向边 (u, v)，它会在 AdjList[u] 和 AdjList[v] 中各出现一次，总共 2E 个条目。对于每条有向边 (u, v)，它只在 AdjList[u] 中出现一次，总共 E 个条目。此外，还需要 V 个列表头部的空间。因此，总的空间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

由此可见，当图是稀疏图（边的数量 E 远小于 V²，例如 E ≈ V 或 E ≈ V log V）时，邻接表的空间效率远高于邻接矩阵。当图是稠密图（边的数量 E 接近 V²）时，邻接矩阵和邻接表的空间开销接近，O(V+E) 会趋近于 O(V²)，但邻接矩阵可能因为更紧凑的存储（数组而不是链表节点）在实际中稍微节省一些空间常数。

何时选择哪种表示？（优劣对比与应用场景）

选择邻接表还是邻接矩阵取决于你的具体需求，主要考虑以下几点：

邻接矩阵的优点与适用场景：

优点：
- 检查任意两个顶点之间是否存在边非常快，仅需 O(1)。
- 添加和删除边也非常快，仅需 O(1)。
适用场景：
- 图是稠密图，即边很多（E 接近 V²）。在这种情况下，邻接矩阵的空间开销与邻接表相近，但操作（检查、添加、删除边）更快。
- 需要频繁进行检查任意两点间是否有边的操作。
- 顶点数量 V 相对较小，V² 的空间是可以接受的。

邻接表的优点与适用场景：

优点：
- 空间效率高，特别是对于稀疏图（E 远小于 V²），空间复杂度为 O(V + E)。
- 查找一个顶点的所有邻居非常高效，时间复杂度为 O(degree(v))，这对于许多图算法（如遍历）很有利。
适用场景：
- 图是稀疏图，这是大多数实际应用中的情况（例如社交网络、互联网链接）。
- 需要处理的图的顶点数量 V 非常大，V² 的空间开销无法承受。
- 需要频繁执行查找一个顶点的所有邻居或对邻居进行遍历的操作（这是图遍历算法如 BFS 和 DFS 的核心）。
- 添加边（不检查是否存在）操作频繁且对性能要求高（O(1)）。

简而言之：
空间 vs. 时间： 邻接矩阵牺牲空间换取某些操作（检查/添加/删除边）的时间效率，而邻接表节省空间但牺牲了这些操作的时间效率（变为与度相关的 O(degree)）。
图的密度： 稠密图倾向于使用邻接矩阵，稀疏图强烈建议使用邻接表。

对图算法的影响

不同的图表示方式也会影响一些图算法的实现和效率：

广度优先搜索 (BFS) 和深度优先搜索 (DFS): 这些遍历算法的核心操作是找到当前访问顶点的所有邻居。邻接表可以在 O(degree(v)) 时间内完成，而邻接矩阵需要 O(V) 时间。因此，对于稀疏图，使用邻接表可以使得总遍历时间更接近 O(V + E)；使用邻接矩阵则可能是 O(V^2)。
最短路径算法 (如 Dijkstra): 这些算法通常也需要高效地访问顶点的邻居来更新距离。邻接表的 O(degree(v)) 优势使其成为实现这些算法时更常见的选择，特别是在稀疏图上。
最小生成树算法 (如 Prim): Prim 算法的一个常见实现也需要查找连接已访问集合和未访问集合的最小权重边，这通常涉及遍历邻居。同样，邻接表在这里通常表现更好。

总的来说，由于大多数实际应用中的图都是稀疏的，并且许多核心图算法都依赖于高效地访问顶点的邻居，因此邻接表在实践中是更常用、更通用的图表示方法。只有在顶点数量相对较小或图非常稠密，并且对 O(1) 边检查有强需求时，才会优先考虑邻接矩阵。

总结

邻接表和邻接矩阵是存储图数据的两种基本且截然不同的方式。邻接矩阵使用固定大小的二维数组，空间开销固定为 O(V²)，但在检查、添加、删除边等操作上提供 O(1) 的时间性能。邻接表使用一个列表数组，空间开销与顶点和边的总数相关 (O(V + E))，特别适合稀疏图，但在检查边和删除边时可能需要 O(degree) 的时间，但在查找邻居和遍历方面效率更高。理解它们的优缺点并根据图的特性和应用场景来选择合适的表示方法，对于高效地处理图问题至关重要。

邻接表和邻接矩阵