手搓邻接表：从零开始理解图数据结构（适合新手小白）

15303105423 · 发表于 2025-6-29 10:37:02

一、简介和特点

邻接表是一种用于存储图（Graph）的数据结构，特别适合稀疏图（边数较少的图）。它通过链表的方式为每个节点维护其相邻节点的信息，既能高效节省空间，又能灵活支持图的动态操作。本文将基于您手写的C++邻接表类，通过代码注释与步骤解析，帮助新手小白理解其核心实现逻辑。

二、优点

1. 空间效率：相较于邻接矩阵（二维数组），邻接表在稀疏图中仅需存储实际存在的边，避免大量无效空间的浪费。

2. 动态扩展：支持节点和边的随时添加，无需提前确定图规模。

3. 操作灵活：通过链表快速定位节点的出边，便于实现深度/广度优先遍历等算法。

三、实现步骤

1. 定义边和节点的结构体：

edge：每条边包含指向下一节点的索引（nextnum）、边权值（data）和指向下一条边的指针（next）。

listnode：每个节点包含节点数据（data）和指向第一条边的指针（first）。

2. 构建图类（graph）：

使用节点数组（g）存储所有节点，节点数（n）记录当前节点数量。

提供两种构造函数：指定节点数初始化或默认初始化为1001个节点。

3. 添加边（addedge(head, tail, data)）：

从节点head指向节点tail，边权值为data。

若head节点无出边，直接创建第一条边；否则遍历链表找到末尾，添加新边。

4. 添加节点（addnode(k, data)）：

在索引k处创建新节点，存储数据data，并更新节点数。

5. 打印图结构（print()）：

遍历所有节点，输出节点数据及其所有出边的目标节点和权值。

四、代码和注释

#include <iostream>
using namespace std;
// 边结构体：存储指向下一节点的索引、边权值、指向下一条边的指针
struct edge {
int nextnum; // 下一节点的索引
int data; // 边权值（可根据需求修改类型）
edge* next = nullptr; // 指向下一条边的指针
};
// 节点结构体：存储节点数据、指向第一条边的指针
struct listnode {
int data; // 节点数据
edge* first = nullptr; // 指向第一条出边
};
// 图类：维护节点数组和节点数
class graph {
listnode* g; // 节点数组
int n = 0; // 当前节点数量
public:
// 构造函数1：指定节点数初始化数组
graph(int num) {
g = new listnode[num];
}
// 构造函数2：默认初始化1001个节点
graph() {
g = new listnode[1001];
}
// 添加边方法
void addedge(int head, int tail, int data) {
// 获取head节点的第一条边
edge* tmp = g[head].first;
if (!tmp) { // 若head无出边，创建第一条边
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; // 末尾标记
}
}
};

复制代码

五、总结

邻接表作为图数据结构的核心实现方式之一，通过链表巧妙平衡了空间与效率。理解其底层逻辑不仅有助于处理图算法问题，更能培养对动态数据结构的抽象思维。本文代码虽为简化版，但已涵盖基础操作框架，可作为学习图数据结构的入门参考。建议进一步探索双向链表优化、权重存储调整等扩展应用。

参考：信奥自学