在 C++ 中实现图的存储时，常用的方法包括 邻接矩阵（Adjacency Matrix）、邻接表（Adjacency List） 和 边列表（Edge List）。以下是具体实现方法、优缺点分析及代码示例：
1. 邻接矩阵（Adjacency Matrix）
原理
- 使用二维数组
matrix[u][v]表示顶点u和v的连接关系。 - 适用于 稠密图（边数接近顶点数的平方）。
- 无权图：
matrix[u][v] = 1表示存在边；0表示无连接。 - 带权图：
matrix[u][v] = weight表示边的权重。
图解
C++ 实现
#include <vector>
using namespace std;// 定义图的顶点数
const int V = 100;// 无权图的邻接矩阵
vector<vector<int>> adjMatrix(V, vector<int>(V, 0));// 添加无向边
void addUndirectedEdge(int u, int v) {adjMatrix[u][v] = 1;adjMatrix[v][u] = 1;
}// 添加带权有向边
void addDirectedWeightedEdge(int u, int v, int weight) {adjMatrix[u][v] = weight;
}// 检查边是否存在
bool hasEdge(int u, int v) {return adjMatrix[u][v] != 0;
}
优点
- 快速判断两顶点是否相邻：时间复杂度 O(1)。
- 适合频繁查询边的存在性。
缺点
- 空间复杂度高：O(V²)，不适合顶点数多（如 V > 1e4）的稀疏图。
- 插入/删除边效率低：需要修改二维数组。
2. 邻接表（Adjacency List）
原理
- 为每个顶点维护一个链表或动态数组，存储其邻接顶点。
- 适用于 稀疏图（边数远小于顶点数的平方）。
- 无权图：
adjList[u]存储v的集合。 - 带权图：
adjList[u]存储pair<v, weight>。
C++ 实现
#include <vector>
#include <list>
using namespace std;// 无权图的邻接表（使用 vector）
vector<vector<int>> adjList;// 初始化顶点数为 n 的图
void initGraph(int n) {adjList.resize(n);
}// 添加无向边
void addUndirectedEdge(int u, int v) {adjList[u].push_back(v);adjList[v].push_back(u);
}// 带权图的邻接表（使用 vector<pair>）
vector<vector<pair<int, int>>> weightedAdjList;// 添加带权有向边
void addWeightedDirectedEdge(int u, int v, int weight) {weightedAdjList[u].emplace_back(v, weight); // C++11 的 emplace_back 更高效
}// 遍历顶点 u 的邻居
void traverseNeighbors(int u) {for (const auto& neighbor : adjList[u]) {// 处理邻居顶点 neighbor}
}
优点
- 空间复杂度低：O(V + E)，适合大规模稀疏图。
- 高效遍历邻接顶点：时间复杂度与邻接顶点数成正比。
缺点
- 查询边的存在性慢：需要遍历邻接表，时间复杂度 O(degree(u))。
3. 边列表（Edge List）
原理
- 将图的边存储为
(u, v, weight)的列表。 - 适用于需要 按边遍历 的场景（如 Kruskal 算法求最小生成树）。
C++ 实现
#include <vector>
using namespace std;// 定义边的结构体
struct Edge {int u, v, weight;Edge(int u, int v, int w) : u(u), v(v), weight(w) {}
};vector<Edge> edgeList;// 添加带权边
void addEdge(int u, int v, int weight) {edgeList.emplace_back(u, v, weight);
}// 遍历所有边
void traverseEdges() {for (const Edge& e : edgeList) {// 处理边 e.u -> e.v，权重 e.weight}
}
优点
- 存储简单：适用于算法需要全局遍历边（如 Kruskal 算法）。
- 节省空间：仅存储存在的边，空间复杂度 O(E)。
缺点
- 查询顶点邻接关系慢：需要遍历整个边列表。
4. 链式前向星（Linked Forward Star）
原理
- 一种紧凑的邻接表实现，通过数组模拟链表，常用于算法竞赛。
- 使用三个数组：
head[]、to[]、next[]和weight[]。
C++ 实现
const int MAX_EDGES = 1e5; // 最大边数
int head[MAX_EDGES]; // head[u] 表示顶点 u 的第一条边的索引
int to[MAX_EDGES]; // 存储边的终点
int next[MAX_EDGES]; // 存储下一条边的索引
int weight[MAX_EDGES]; // 存储边的权重
int edgeCount = 0; // 当前边数// 初始化
void init() {memset(head, -1, sizeof(head)); // 初始化为 -1
}// 添加有向边 u -> v，权重 w
void addEdge(int u, int v, int w) {to[edgeCount] = v;weight[edgeCount] = w;next[edgeCount] = head[u];head[u] = edgeCount++;
}// 遍历顶点 u 的邻接边
void traverseEdges(int u) {for (int i = head[u]; i != -1; i = next[i]) {int v = to[i];int w = weight[i];// 处理边 u -> v，权重 w}
}
优点
- 内存紧凑：适合处理超大规模图（如顶点数 1e5 以上）。
- 高效遍历：与邻接表性能接近。
缺点
- 实现复杂：需要手动管理数组索引。
5. 存储方法对比及适用场景
| 存储方法 | 时间复杂度（查询边） | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | O(1) | O(V²) | 稠密图、频繁查询边的存在性 |
| 邻接表 | O(degree(u)) | O(V + E) | 稀疏图、频繁遍历邻接顶点 |
| 边列表 | O(E) | O(E) | 需要全局遍历边的算法 |
| 链式前向星 | O(degree(u)) | O(V + E) | 算法竞赛中的大规模图处理 |
6. 动态图的存储优化
- 邻接表的动态扩展：使用
vector的push_back动态添加边。 - 删除边的优化：使用链表（如
list）或标记法（惰性删除）。
总结
- 邻接矩阵：适合稠密图，快速查询边的存在性。
- 邻接表：适合稀疏图，高效遍历邻接顶点（推荐使用
vector<vector<pair<int, int>>>）。 - 边列表：适合需要全局处理边的场景（如 Kruskal 算法）。
- 链式前向星：适合算法竞赛中的高性能需求。
代码建议：大多数情况下优先使用 邻接表，结合 C++ 的 vector 和 pair 实现带权图的高效存储。
