在 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
实现带权图的高效存储。