一、简介和特点 邻接表是一种常用的图存储结构，它使用链表来表示图中顶点之间的邻接关系。本文实现的邻接表类可以高效地表示稀疏图，并支持动态添加顶点和边。
主要特点：
空间效率：特别适合存储稀疏图 动态扩展：可以灵活添加顶点和边 直观表示：直接反映图的连接关系 权重支持：可以存储边的权重信息 简单接口：提供基本的图操作功能 二、与其他实现的优点 相比邻接矩阵实现，这种邻接表实现有以下优势：
1.空间节省：只存储实际存在的边
2.动态扩展：无需预先确定图的大小
3.高效遍历：可以快速访问某个顶点的所有邻接点
4.权重灵活：每条边可以存储不同的权重值
5.实现简洁：指针操作直观反映图结构
三、实现步骤解析
定义边结构：创建包含目标顶点、边数据和next指针的边节点
定义顶点结构：创建包含顶点数据和第一条边指针的顶点节点
图类设计：
提供默认和指定大小的构造函数
维护顶点计数器
核心操作实现：
添加边：在指定顶点的边链表中插入新边
添加顶点：设置顶点数据并增加计数
辅助功能：
打印整个图的邻接表表示
四、完整代码和注释
C++
#include
// 边结构体，表示图中的边 struct edge { int nextnum; // 边指向的顶点编号 int data; // 边存储的数据(如权重) edge* next=nullptr; // 指向下一条边的指针 };
// 顶点结构体，表示图中的顶点 struct listnode { int data; // 顶点存储的数据 edge* first=nullptr;// 指向第一条边的指针 };
// 图类，使用邻接表实现 class graph{ listnode* g; // 邻接表数组 int n = 0; // 顶点计数器
public: // 指定大小的构造函数 graph(int num){ g = new listnode[num]; // 分配顶点数组 }
// 默认构造函数(默认大小1001)
graph(){
g = new listnode[1001];
}
// 添加边的方法
void addedge(int head, int tail, int data){
edge* tmp = g[head].first; // 获取顶点的第一条边
// 如果顶点没有边，直接添加为第一条边
if (!tmp) {
g[head].first = new edge;
g[head].first->data = data;
g[head].first->nextnum = tail;
}
else {
// 否则遍历到边链表末尾添加新边
while (tmp->next)
tmp = tmp->next;
tmp->next = new edge;
tmp->next->data = data;
tmp->next->nextnum = tail;
}
}
// 添加顶点的方法
void addnode(int k, int data){
g[k].data = data; // 设置顶点数据
n++; // 增加顶点计数
}
// 打印图的邻接表表示
void print(){
for (int i = 0;i < n;i++){
cout << g[i].data << "->"; // 打印顶点数据
edge* tmp = g[i].first; // 获取第一条边
// 遍历打印所有邻接边
while (tmp) {
cout << tmp->nextnum<<"("<<tmp->data << ")->";
tmp = tmp->next;
}
cout <<"null"<< endl; // 边链表结束标记
}
}}; 五、总结 本文介绍了一种邻接表实现的图数据结构，通过详细的代码注释和分步解析，展示了图的基本操作实现。邻接表在表示稀疏图时具有明显的空间优势，适合处理顶点多但边相对少的图结构。理解这种实现方式对于学习图算法和网络分析有重要意义。
