邻接矩阵 vs 邻接表：图数据结构 C++ 实现与 3 大性能场景对比

邻接矩阵 vs 邻接表：图数据结构 C++ 实现与 3 大性能场景对比

在计算机科学中，图（Graph）是一种非常重要的非线性数据结构，它由一组顶点（Vertex）和连接这些顶点的边（Edge）组成。图结构广泛应用于社交网络、路由算法、推荐系统等领域。本文将深入探讨图的两种主要存储结构——邻接矩阵和邻接表，并通过C++实现展示它们在不同场景下的性能表现。

1. 图数据结构基础

图结构之所以重要，是因为它能够直观地表示现实世界中各种复杂的关系网络。与线性结构（如数组、链表）和树形结构不同，图中的元素可以任意连接，形成多对多的关系。

1.1 图的分类

根据边的性质，图可以分为以下几种类型：

• 无向图：边没有方向性，表示双向关系
• 有向图：边有方向性，表示单向关系
• 带权图：边带有权重值，表示关系的强度或成本

1.2 图的存储方式对比

注：V表示顶点数，E表示边数，degree表示顶点的度数

2. C++实现：邻接矩阵

邻接矩阵使用二维数组来表示图中顶点之间的连接关系。对于无权图，矩阵元素为0或1；对于带权图，则存储相应的权重值。

2.1 基本实现

#include <iostream> #include <vector> class AdjMatrixGraph { private: int vertexCount; std::vector<std::vector<int>> matrix; public: AdjMatrixGraph(int n) : vertexCount(n), matrix(n, std::vector<int>(n, 0)) {} void addEdge(int u, int v, int weight = 1) { matrix[u][v] = weight; matrix[v][u] = weight; // 无向图需要双向设置 } void removeEdge(int u, int v) { matrix[u][v] = 0; matrix[v][u] = 0; } bool hasEdge(int u, int v) const { return matrix[u][v] != 0; } void print() const { for (const auto& row : matrix) { for (int val : row) { std::cout << val << " "; } std::cout << std::endl; } } };

2.2 性能特点

• 优点：

  • 查询任意两顶点间是否有边非常高效（O(1)）
  • 实现简单直观
  • 适合稠密图（边数接近顶点数平方）

• 缺点：

  • 空间复杂度高（O(V²)）
  • 添加/删除顶点成本高（需要重新分配矩阵）
  • 遍历邻接点效率低（需要检查所有顶点）

3. C++实现：邻接表

邻接表使用数组+链表的结构，为每个顶点维护一个链表，存储其邻接顶点。这种结构更节省空间，特别适合稀疏图。

3.1 基本实现

#include <iostream> #include <vector> #include <list> class AdjListGraph { private: struct Edge { int dest; int weight; Edge(int d, int w = 1) : dest(d), weight(w) {} }; int vertexCount; std::vector<std::list<Edge>> adjLists; public: AdjListGraph(int n) : vertexCount(n), adjLists(n) {} void addEdge(int u, int v, int weight = 1) { adjLists[u].emplace_back(v, weight); adjLists[v].emplace_back(u, weight); // 无向图需要双向添加 } void removeEdge(int u, int v) { adjLists[u].remove_if([v](const Edge& e) { return e.dest == v; }); adjLists[v].remove_if([u](const Edge& e) { return e.dest == u; }); } bool hasEdge(int u, int v) const { for (const auto& edge : adjLists[u]) { if (edge.dest == v) return true; } return false; } void print() const { for (int i = 0; i < vertexCount; ++i) { std::cout << i << ": "; for (const auto& edge : adjLists[i]) { std::cout << "-> " << edge.dest << "(" << edge.weight << ") "; } std::cout << std::endl; } } };

3.2 性能特点

• 优点：

  • 空间效率高（O(V+E)）
  • 添加顶点容易
  • 遍历邻接点效率高（只需遍历链表）
  • 适合稀疏图

• 缺点：

  • 查询特定边效率较低（O(degree)）
  • 实现稍复杂
  • 删除边操作成本较高（需要遍历链表）

4. 三大性能场景对比

4.1 稠密图场景

稠密图是指边数接近最大可能边数（V*(V-1)/2）的图。在这种场景下：

• 邻接矩阵：虽然空间占用大，但查询效率极高
• 邻接表：空间优势不明显，链表遍历开销增大

实测数据（V=1000，E≈500000）：

4.2 稀疏图场景

稀疏图是指边数远小于最大可能边数的图。在这种场景下：

• 邻接表：空间优势明显，遍历邻接点效率高
• 邻接矩阵：大量空间被浪费在存储不存在的边上

实测数据（V=1000，E≈2000）：

4.3 频繁查询边场景

某些应用（如路由算法）需要频繁检查两点间是否存在边：

• 邻接矩阵：恒定时间O(1)查询
• 邻接表：需要遍历链表，效率取决于顶点度数

实测数据（V=1000，E=3000，查询100000次）：

5. 选型决策指南

在实际项目中，选择图的存储结构应考虑以下因素：

1. 图的密度：

   • 稠密图（E ≈ V²）：优先考虑邻接矩阵
   • 稀疏图（E ≪ V²）：优先考虑邻接表

2. 操作频率：

   • 频繁查询边存在性：邻接矩阵更优
   • 频繁遍历邻接点：邻接表更优

3. 内存限制：

   • 内存充足：邻接矩阵可能更简单
   • 内存紧张：必须使用邻接表

4. 动态性需求：

   • 频繁添加/删除顶点：邻接表更灵活
   • 固定顶点数：两者均可

决策流程图

开始 │ ↓ 是否需要频繁查询特定边？ ├─ 是 → 使用邻接矩阵 ↓ 否 │ ↓ 图是否非常稠密（E > VlogV）？ ├─ 是 → 使用邻接矩阵 ↓ 否 │ ↓ 内存是否非常紧张？ ├─ 是 → 使用邻接表 ↓ 否 │ ↓ 是否需要频繁添加/删除顶点？ ├─ 是 → 使用邻接表 ↓ 否 │ ↓ 根据个人偏好选择

6. 高级优化技巧

6.1 邻接表的优化实现

对于性能要求高的场景，可以用vector代替list，并用排序+二分查找来优化查询：

class OptimizedAdjListGraph { private: int vertexCount; std::vector<std::vector<std::pair<int, int>>> adjLists; // (dest, weight) public: // ... 其他方法同上 void addEdge(int u, int v, int weight = 1) { adjLists[u].emplace_back(v, weight); adjLists[v].emplace_back(u, weight); // 保持有序以便二分查找 std::sort(adjLists[u].begin(), adjLists[u].end()); std::sort(adjLists[v].begin(), adjLists[v].end()); } bool hasEdge(int u, int v) const { const auto& edges = adjLists[u]; return std::binary_search(edges.begin(), edges.end(), std::make_pair(v, 0), [](const auto& a, const auto& b) { return a.first < b.first; }); } };

6.2 邻接矩阵的压缩存储

对于稀疏图，邻接矩阵可以采用以下压缩方式：

1. CSR（Compressed Sparse Row）格式：

   • 存储非零元素的值、列索引和行偏移
   • 大幅减少空间占用，同时保持矩阵特性

2. 位矩阵：

   • 对于无权图，用单个bit表示边的存在性
   • 空间节省8倍（相比int矩阵）

7. 实际应用案例分析

7.1 社交网络分析

在社交网络（如Facebook好友关系）中：

• 特点：海量用户（顶点），但平均好友数（边）有限
• 选择：邻接表更合适，因为：
  • 极度稀疏（每人约几百好友，相比可能的上百万用户）
  • 需要频繁遍历用户的好友列表
  • 很少需要查询两个特定用户是否直接是好友

7.2 路由算法

在网络路由（如OSPF协议）中：

• 特点：路由器数量相对固定，需要频繁查询最短路径
• 选择：邻接矩阵更合适，因为：
  • 网络通常较稠密（路由器间多有连接）
  • 需要频繁查询任意两点间连接状态
  • 算法（如Floyd-Warshall）基于矩阵运算

7.3 推荐系统

在商品推荐（如"购买此商品的顾客也买了"）中：

• 特点：商品和用户数量巨大，关系稀疏
• 选择：邻接表的变体（如压缩稀疏行格式），因为：
  • 需要高效遍历关联商品
  • 存储空间是关键考量
  • 可结合哈希表加速特定查询