邻接表是图的链式存储：对每个顶点建一个单链表，存与该顶点邻接的顶点。结构由顶点表（数组，含顶点数据 + 指向第一条边的指针）和边表（弧结点）（含邻接点下标、权值可选、指向下一条边的指针）组成。
typedef struct ArcNode { // 边结点
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一条边
} ArcNode;
typedef struct VNode { // 顶点结点
char data; // 顶点数据
ArcNode *first; // 指向第一条边
} VNode, AdjList[MaxVertexNum];
typedef struct {
AdjList vertices; // 顶点表
int vexnum, arcnum; // 顶点数、边数
} ALGraph;| 性质 | 说明 |
|---|---|
| 空间复杂度 | O(n+e)：n 个顶点表 + 2e 个边结点（无向图） |
| 无向图边结点数 | 2e（每条边在两个链表中各出现一次） |
| 有向图边结点数 | e |
| 求无向图度 | 遍历该顶点链表，O(deg) |
| 求有向图出度 / 入度 | 出度 O(OD)；入度需遍历所有链表，最坏 O(n+e) |
| 判断边存在 | 遍历该顶点链表，O(deg(u)) |
| 不唯一性 | 边上插入顺序不同 → 不同邻接表 |
| 比较项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²) | O(n+e) |
| 判断边存在 | O(1) | O(度) |
| 求度 | O(n) | O(度) |
| 适用 | 稠密图 | 稀疏图 |
| 唯一性 | 唯一（给定编号） | 不唯一 |
| 考法 | 解题套路 |
|---|---|
| 写出邻接表 | 对每个顶点列出其所有邻接点 |
| 空间复杂度 | O(n+e) |
| 从邻接表求度 | 遍历链表计数 |
| 选存储结构 | 稀疏图→邻接表，稠密图→邻接矩阵 |
| 有向图求入度 | 遍历所有链表或用逆邻接表 |
↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。