c++实现邻接表（附带源码）
一、项目背景详细介绍
在图论与算法学习中，“图（Graph）”是一种极其重要的数据结构。它能表示对象之间的各种关系，例如社交网络中的“好友关系”、交通系统中的“路径连接”、计算机网络中的“路由连接”、编译器中的“依赖图”、AI 中的“状态转移图”等。
图有两种常见表示方式：
-
邻接矩阵（Adjacency Matrix）：使用二维数组表示顶点间的边，适合稠密图；
-
邻接表（Adjacency List）：每个顶点维护一条链表（或向量）保存其邻接点，适合稀疏图。
在稀疏图（即边数远小于 n2n^2n2 的场景）中，邻接表的存储效率远优于邻接矩阵。例如：
-
社交网络中一个用户可能只与极少数其他人有联系；
-
地图中一个城市只与少数邻近城市相连；
-
项目依赖图中一个任务通常只依赖少量其他任务。
因此，在现代图算法（如 Dijkstra、BFS、DFS、Kruskal、Prim、拓扑排序等）的实现中，邻接表是最常用的基础数据结构。
本项目旨在用 现代 C++（C++17） 实现一个灵活、通用、可复用的邻接表类（支持有向图/无向图、带权图/无权图），并提供典型的图算法操作接口（如插入边、删除边、遍历、输出结构等）。
通过完整的教学实现，读者可以深入理解图的结构组织、存储方式、算法接口设计与工程化实现。
二、项目需求详细介绍
功能性需求：
-
实现一个
Graph类（模板化或整型顶点）：-
支持创建指定顶点数的图；
-
支持 有向/无向图；
-
支持 带权边；
-
提供基础操作：
-
添加边（
addEdge(u, v, weight)）； -
删除边；
-
输出图结构；
-
获取某个顶点的邻接列表；
-
-
提供 BFS（广度优先搜索） 与 DFS（深度优先搜索）；
-
支持检测图是否连通。
-
-
输出示例：
-
创建一个图；
-
添加若干边；
-
输出邻接表；
-
执行 DFS 与 BFS。
-
三、相关技术详细介绍
1. 图的基本概念
图由两部分组成：
-
顶点（Vertex）：表示对象；
-
边（Edge）：表示顶点间的关系，可带权值。
图可分为：
-
有向图（Directed Graph）：边具有方向 (u → v)；
-
无向图（Undirected Graph）：边无方向 (u — v)。
2. 邻接表的结构
邻接表的核心思想是：
每个顶点都有一个“邻接链表”，存储与其相连的顶点及对应权值。
示例：
0: (1,5) (2,3)
1: (0,5) (3,2)
2: (0,3)
3: (1,2)
表示一个无向带权图：
-
0 ↔ 1 权值 5；
-
0 ↔ 2 权值 3；
-
1 ↔ 3 权值 2。
3. 邻接表与邻接矩阵对比
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储复杂度 | O(n²) | O(n + m) |
| 适用场景 | 稠密图 | 稀疏图 |
| 查询某条边 | O(1) | O(度(u)) |
| 枚举邻居 | O(n) | O(度(u)) |
| 添加顶点 | 较复杂 | 较简单 |
4. C++ STL 设计
-
使用
std::vector<std::vector<std::pair<int, int>>> adj; -
其中：
-
adj[u]：顶点u的邻接列表； -
pair<int,int>：存储(v, weight)；
-
-
对于无权图，权值可默认 1 或忽略。
四、实现思路详细介绍
-
类结构设计：
class Graph {
int V; // 顶点数
bool directed; // 是否为有向图
std::vector<std::vector<std::pair<int,int>>> adj; // 邻接表
};
-
主要成员函数：
-
Graph(int V, bool directed=false)：构造函数； -
void addEdge(int u, int v, int w=1)：添加边； -
void removeEdge(int u, int v)：删除边； -
void printGraph()：输出邻接表； -
void BFS(int start)：广度优先搜索； -
void DFS(int start)：深度优先搜索； -
bool isConnected()：判断图是否连通。
-
-
算法实现策略：
-
BFS 用
queue； -
DFS 用递归；
-
visited数组标记访问状态； -
输出顺序方便教学展示。
-
五、完整实现代码
/*************************************************************
* 文件名: adjacency_list.cpp
* 功能: 使用C++17实现邻接表图结构（支持有向/无向、带权图）
* 编译:
* g++ -std=c++17 -O2 -Wall -o adjacency_list adjacency_list.cpp
* 运行:
* ./adjacency_list
*************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <iomanip>
class Graph {
private:
int V; // 顶点数量
bool directed; // 是否为有向图
std::vector<std::vector<std::pair<int,int>>> adj; // 邻接表 (顶点, 权值)
public:
// 构造函数
Graph(int vertices, bool isDirected = false)
: V(vertices), directed(isDirected), adj(vertices) {}
// 添加边
void addEdge(int u, int v, int w = 1) {
if (u >= V || v >= V) {
std::cerr << "错误: 顶点超出范围！" << std::endl;
return;
}
adj[u].push_back({v, w});
if (!directed) {
adj[v].push_back({u, w});
}
}
// 删除边
void removeEdge(int u, int v) {
if (u >= V || v >= V) return;
auto &list = adj[u];
list.erase(
std::remove_if(list.begin(), list.end(),
[v](auto &p){ return p.first == v; }),
list.end());
if (!directed) {
auto &list2 = adj[v];
list2.erase(
std::remove_if(list2.begin(), list2.end(),
[u](auto &p){ return p.first == u; }),
list2.end());
}
}
// 打印邻接表
void printGraph() const {
std::cout << "图的邻接表表示：" << std::endl;
for (int i = 0; i < V; ++i) {
std::cout << "顶点 " << i << " -> ";
for (auto &[v, w] : adj[i]) {
std::cout << "(" << v << ",权=" << w << ") ";
}
std::cout << std::endl;
}
}
// BFS（广度优先搜索）
void BFS(int start) const {
if (start >= V) return;
std::vector<bool> visited(V, false);
std::queue<int> q;
q.push(start);
visited[start] = true;
std::cout << "BFS遍历顺序: ";
while (!q.empty()) {
int u = q.front(); q.pop();
std::cout << u << " ";
for (auto &[v, w] : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
std::cout << std::endl;
}
// DFS（递归实现）
void DFSUtil(int u, std::vector<bool> &visited) const {
visited[u] = true;
std::cout << u << " ";
for (auto &[v, w] : adj[u]) {
if (!visited[v]) {
DFSUtil(v, visited);
}
}
}
void DFS(int start) const {
if (start >= V) return;
std::vector<bool> visited(V, false);
std::cout << "DFS遍历顺序: ";
DFSUtil(start, visited);
std::cout << std::endl;
}
// 判断是否连通（无向图）
bool isConnected() const {
if (directed) {
std::cerr << "警告: 连通性检测仅适用于无向图。" << std::endl;
return false;
}
std::vector<bool> visited(V, false);
DFSUtil(0, visited);
for (bool v : visited) {
if (!v) return false;
}
return true;
}
};
/************** 主函数（测试示例） **************/
int main() {
// 创建一个5个顶点的无向带权图
Graph g(5, false);
g.addEdge(0, 1, 2);
g.addEdge(0, 4, 1);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 8);
g.addEdge(1, 4, 5);
g.addEdge(2, 3, 7);
g.addEdge(3, 4, 4);
std::cout << "===== 图结构演示 =====" << std::endl;
g.printGraph();
std::cout << "\n===== 遍历演示 =====" << std::endl;
g.BFS(0);
g.DFS(0);
std::cout << "\n===== 连通性检测 =====" << std::endl;
bool conn = g.isConnected();
std::cout << (conn ? "图是连通的" : "图不是连通的") << std::endl;
return 0;
}
六、代码详细解读
-
Graph(int vertices, bool isDirected)：构造函数，初始化图的顶点数与方向类型；
-
addEdge(u, v, w)：在
u到v添加一条权值为w的边；若无向则反向添加； -
removeEdge(u, v)：删除两顶点间的连接；
-
printGraph()：以文本形式输出邻接表；
-
BFS(start)：层次遍历，使用
queue； -
DFS(start)：深度遍历，递归实现；
-
isConnected()：在无向图上检测是否所有顶点可达。
七、项目详细总结
本项目从零实现了邻接表的存储结构与基本算法，完整展示了：
-
图结构的设计与存储；
-
邻接表与矩阵的比较；
-
BFS / DFS 的核心逻辑；
-
STL 在图算法中的应用；
-
有向与无向的统一设计方法。
邻接表在现实应用中极为广泛，是理解复杂图算法（Dijkstra、Prim、Kruskal、拓扑排序）的基石。
八、项目常见问题及解答
Q1：为什么使用 vector<pair<int,int>> 而不是 list？
A1：因为大多数算法需要随机访问和排序，vector 更高效。
Q2：如何实现无权图？
A2：可在添加边时忽略 w 参数或设默认值 1。
Q3：是否可以支持字符顶点（如 A、B、C）？
A3：可以，将顶点映射为整数索引（如 A→0）。
Q4：BFS 和 DFS 有什么区别？
A4：BFS 层次遍历，优先访问距离近的顶点；DFS 深度优先，沿一条路径走到底再回溯。
Q5：为什么 isConnected 不适用于有向图？
A5：因为有向图的连通性需要判断“强连通分量”，需要 Tarjan/Kosaraju 算法。
九、扩展方向与性能优化
-
带权最短路径：在邻接表上实现 Dijkstra、Bellman-Ford；
-
最小生成树：实现 Prim 或 Kruskal；
-
拓扑排序：针对有向无环图（DAG）；
-
强连通分量检测：基于 Tarjan 算法；
-
图可视化导出：将邻接表输出为 Graphviz
.dot文件； -
模板化设计：使顶点类型可泛化为字符串、类对象；
-
性能优化：使用
std::unordered_map<int, vector<pair<int,int>>>存稀疏图； -
动态图：支持在线添加/删除顶点。
更多推荐
30
0- 0
已为社区贡献68条内容
所有评论(0)