邻接表转逆邻接表：C语言实现与图解教程（附完整代码）
邻接表转逆邻接表：C语言实现与图解教程（附完整代码）
在数据结构与算法领域，图的存储方式直接影响着算法的效率与实现复杂度。邻接表作为最常用的图存储结构之一，以其空间效率高、易于遍历邻接节点的特点广受欢迎。然而在某些场景下，我们需要快速获取"哪些节点指向当前节点"而非"当前节点指向哪些节点"，这时逆邻接表就派上了用场。本文将手把手带你用C语言实现邻接表到逆邻接表的转换，通过图解+代码的双重解析，让初学者也能彻底掌握这一核心技能。
1. 图的基础：邻接表与逆邻接表对比
1.1 邻接表的结构解析
邻接表采用数组+链表的方式存储图：
- 顶点表：用数组存储各顶点信息，每个数组元素包含：
typedef struct VNode { int data; // 顶点数据 ArcNode *first; // 指向第一条边 } VNode; - 边表：链表节点表示从该顶点出发的边：
typedef struct ArcNode { int adjvex; // 指向的顶点位置 ArcNode *next; // 下一条边指针 } ArcNode;
示例：对于边A→B，A的边表中会有一个节点指向B。
1.2 逆邻接表的本质
逆邻接表是邻接表的"反向版本"，其核心差异在于：
- 边表存储的是指向该顶点的边而非从该顶点出发的边
- 边A→B在逆邻接表中表现为：B的边表包含指向A的节点
对比表格：
| 特性 | 邻接表 | 逆邻接表 |
|---|---|---|
| 边表含义 | 出边 | 入边 |
| 空间复杂度 | O( | V |
| 查询效率 | 快速获取出边 | 快速获取入边 |
| 典型应用 | DFS/BFS遍历 | 拓扑排序、关键路径 |
提示：逆邻接表特别适合需要频繁查询节点入度的场景，比如拓扑排序中需要不断查找入度为0的节点。
2. 转换算法的核心思路
2.1 算法流程图解
转换过程可分为三个关键步骤：
- 初始化逆邻接表的顶点数组
- 遍历原邻接表的每个顶点
- 对每个顶点的每条边，在逆邻接表中创建反向边
graph TD A[开始] --> B[初始化逆邻接表顶点数组] B --> C[遍历邻接表顶点i] C --> D[遍历顶点i的所有边i→j] D --> E[在逆邻接表中创建边j→i] E --> F{是否遍历完所有边?} F -- 否 --> D F -- 是 --> G{是否遍历完所有顶点?} G -- 否 --> C G -- 是 --> H[结束]2.2 时间复杂度分析
- 需要遍历所有顶点：O(|V|)
- 对每个顶点遍历其所有边：O(|E|)
- 总时间复杂度：O(|V|+|E|)
3. C语言完整实现
3.1 数据结构定义
首先定义图的最大顶点数和基本结构体：
#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 // 最大顶点数 // 边表节点 typedef struct ArcNode { int adjvex; // 指向的顶点位置 struct ArcNode *next; // 下一条边指针 } ArcNode; // 顶点表节点 typedef struct VNode { int data; // 顶点信息 ArcNode *first; // 第一条边指针 } VNode, AdjList[MAX_VERTEX_NUM]; // 图结构 typedef struct { AdjList vertices; // 顶点数组 int vexnum, arcnum; // 顶点数和边数 } ALGraph;3.2 邻接表创建函数
void CreateALGraph(ALGraph *G) { printf("输入顶点数和边数: "); scanf("%d %d", &G->vexnum, &G->arcnum); // 初始化顶点表 for (int i = 1; i <= G->vexnum; i++) { G->vertices[i].data = i; G->vertices[i].first = NULL; } // 建立边表 printf("输入%d条边(格式: 起点 终点):\n", G->arcnum); for (int k = 0; k < G->arcnum; k++) { int u, v; scanf("%d %d", &u, &v); ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = v; p->next = G->vertices[u].first; // 头插法 G->vertices[u].first = p; } }3.3 核心转换函数
void ConvertToInverse(ALGraph *G, ALGraph *GInverse) { GInverse->vexnum = G->vexnum; GInverse->arcnum = G->arcnum; // 初始化逆邻接表顶点 for (int i = 1; i <= GInverse->vexnum; i++) { GInverse->vertices[i].data = G->vertices[i].data; GInverse->vertices[i].first = NULL; } // 转换核心逻辑 for (int u = 1; u <= G->vexnum; u++) { ArcNode *p = G->vertices[u].first; while (p != NULL) { int v = p->adjvex; // 创建反向边 ArcNode *s = (ArcNode*)malloc(sizeof(ArcNode)); s->adjvex = u; s->next = GInverse->vertices[v].first; GInverse->vertices[v].first = s; p = p->next; } } }4. 实例演示与测试
4.1 测试用例图解
以6个顶点8条边的有向图为例：
输入： 6 8 1 2 1 4 4 2 2 5 5 4 3 5 3 6 6 6邻接表结构：
1 -> 4 -> 2 2 -> 5 3 -> 6 -> 5 4 -> 2 5 -> 4 6 -> 6转换后的逆邻接表：
1 -> 2 -> 4 -> 1 3 -> 4 -> 5 -> 1 5 -> 3 -> 2 6 -> 6 -> 34.2 打印函数实现
为验证结果，实现打印函数：
void PrintGraph(ALGraph *G) { printf("顶点数: %d, 边数: %d\n", G->vexnum, G->arcnum); for (int i = 1; i <= G->vexnum; i++) { printf("[%d]", G->vertices[i].data); ArcNode *p = G->vertices[i].first; while (p != NULL) { printf(" -> %d", p->adjvex); p = p->next; } printf("\n"); } }4.3 主函数测试
int main() { ALGraph G, GInverse; // 创建邻接表 CreateALGraph(&G); printf("\n原始邻接表:\n"); PrintGraph(&G); // 转换为逆邻接表 ConvertToInverse(&G, &GInverse); printf("\n逆邻接表:\n"); PrintGraph(&GInverse); return 0; }5. 常见问题与优化技巧
5.1 内存管理注意事项
- 每次malloc后应在程序结束时free
- 推荐添加销毁函数：
void DestroyGraph(ALGraph *G) { for (int i = 1; i <= G->vexnum; i++) { ArcNode *p = G->vertices[i].first; while (p != NULL) { ArcNode *temp = p; p = p->next; free(temp); } } }
5.2 性能优化方向
- 空间优化：对于稀疏图，邻接表/逆邻接表比邻接矩阵更省空间
- 时间优化：如果需要同时频繁访问出边和入边，可同时维护两种结构
- 并行处理：大规模图处理时，可对不同的顶点分区并行转换
5.3 调试技巧
- 打印中间结果验证每个顶点的转换
- 使用小型测试用例（如3个顶点的完全图）人工验证
- 检查内存泄漏工具如Valgrind
在实际项目中遇到过一个典型错误：忘记初始化逆邻接表顶点的first指针为NULL，导致边表连接异常。这个bug让我花了两个小时才定位到，所以特别提醒初学者注意指针初始化的细节。