邻接表转逆邻接表：C语言实现与图解教程（附完整代码）

邻接表转逆邻接表C语言实现与图解教程附完整代码在数据结构与算法领域图的存储方式直接影响着算法的效率与实现复杂度。邻接表作为最常用的图存储结构之一以其空间效率高、易于遍历邻接节点的特点广受欢迎。然而在某些场景下我们需要快速获取哪些节点指向当前节点而非当前节点指向哪些节点这时逆邻接表就派上了用场。本文将手把手带你用C语言实现邻接表到逆邻接表的转换通过图解代码的双重解析让初学者也能彻底掌握这一核心技能。1. 图的基础邻接表与逆邻接表对比1.1 邻接表的结构解析邻接表采用数组链表的方式存储图顶点表用数组存储各顶点信息每个数组元素包含typedef struct VNode { int data; // 顶点数据 ArcNode *first; // 指向第一条边 } VNode;边表链表节点表示从该顶点出发的边typedef struct ArcNode { int adjvex; // 指向的顶点位置 ArcNode *next; // 下一条边指针 } ArcNode;示例对于边A→BA的边表中会有一个节点指向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让我花了两个小时才定位到所以特别提醒初学者注意指针初始化的细节。