【附C源码】基于邻接表的图结构实现与算法实践图Graph作为非线性数据结构的核心成员在社交网络分析、路径规划、依赖管理等领域有着广泛应用。本文将介绍一种基于邻接表的图结构C语言实现涵盖基础操作、遍历算法以及最短路径求解。一、存储结构设计邻接表是图的一种链式存储结构由顶点数组和边链表组成。对于稀疏图而言相较于邻接矩阵邻接表能够显著降低空间复杂度。1.1 数据结构定义// 边节点typedefstructEdgeNode{intdest;// 目标顶点索引intweight;// 边权重structEdgeNode*next;// 下一条边}EdgeNode;// 顶点节点typedefstructVertex{intdata;// 顶点数据EdgeNode*firstEdge;// 邻接边链表头指针}Vertex;// 图结构typedefstruct{Vertex*vertices;// 顶点数组intvertexCount;// 当前顶点数intcapacity;// 容量上限bool isDirected;// 有向/无向标识}Graph;上述设计中EdgeNode采用头插法构建链表这使得边插入操作的时间复杂度为O(1)。isDirected字段用于区分有向图与无向图后者在添加边时需要同时维护双向关系。1.2 内存布局示意Vertex1Vertex0Graphvertices指针Vertex数组vertexCountcapacityisDirecteddata0EdgeNodedest1weight10EdgeNodedest2weight5NULLdata1EdgeNodedest2weight2NULL二、核心操作实现2.1 图的创建与销毁图的初始化需要分配顶点数组空间并将各顶点的边链表置空Graph*graphCreate(intcapacity,bool isDirected){Graph*g(Graph*)malloc(sizeof(Graph));g-vertices(Vertex*)malloc(sizeof(Vertex)*capacity);for(inti0;icapacity;i){g-vertices[i].firstEdgeNULL;}g-vertexCount0;g-capacitycapacity;g-isDirectedisDirected;returng;}销毁操作需遍历所有顶点释放其边链表节点最后释放顶点数组和图结构本身。此处需注意避免内存泄漏尤其是边节点的逐个释放。2.2 边的添加与删除无向图的边添加需要维护两个方向的链接boolgraphAddEdge(Graph*g,intfrom,intto,intweight){// 创建正向边EdgeNode*newEdge(EdgeNode*)malloc(sizeof(EdgeNode));newEdge-destto;newEdge-weightweight;newEdge-nextg-vertices[from].firstEdge;g-vertices[from].firstEdgenewEdge;// 无向图需添加反向边if(!g-isDirected){EdgeNode*reverseEdge(EdgeNode*)malloc(sizeof(EdgeNode));reverseEdge-destfrom;reverseEdge-weightweight;reverseEdge-nextg-vertices[to].firstEdge;g-vertices[to].firstEdgereverseEdge;}returntrue;}边删除操作相对复杂需要遍历链表定位目标节点并正确处理头节点的特殊情况。无向图的边删除同样需要双向处理。2.3 顶点删除顶点删除是图操作中最复杂的部分涉及以下步骤删除该顶点的所有出边遍历其他顶点删除指向该顶点的入边调整受影响的边目标索引因为顶点数组发生移动压缩顶点数组是否是否开始删除顶点v删除v的所有出边遍历其他顶点存在指向v的边?删除该边目标索引v?目标索引减1继续遍历顶点数组前移vertexCount减1该操作的时间复杂度为O(V E)其中V为顶点数E为边数。三、图遍历算法3.1 深度优先搜索DFSDFS采用递归实现沿着一条路径尽可能深入直至无法继续后回溯voidgraphDFSHelper(Graph*g,intindex,bool*visited){visited[index]true;printf(%d ,g-vertices[index].data);EdgeNode*edgeg-vertices[index].firstEdge;while(edge){if(!visited[edge-dest]){graphDFSHelper(g,edge-dest,visited);}edgeedge-next;}}DFS的时间复杂度为O(V E)空间复杂度取决于递归深度最坏情况下为O(V)。3.2 广度优先搜索BFSBFS借助队列实现按层次遍历图的节点voidgraphBFS(Graph*g,intstartIndex){bool*visited(bool*)calloc(g-vertexCount,sizeof(bool));Queue*qqueueCreate(g-vertexCount1);visited[startIndex]true;queueEnqueue(q,startIndex);while(!queueIsEmpty(q)){intindex;queueDequeue(q,index);printf(%d ,g-vertices[index].data);// 将未访问的邻接顶点入队EdgeNode*edgeg-vertices[index].firstEdge;while(edge){if(!visited[edge-dest]){visited[edge-dest]true;queueEnqueue(q,edge-dest);}edgeedge-next;}}}BFS同样具有O(V E)的时间复杂度但空间复杂度为O(V)用于维护队列和访问标记数组。四、最短路径算法4.1 Dijkstra算法实现Dijkstra算法用于求解单源最短路径要求图中不存在负权边。本实现采用简单数组选择最小距离顶点时间复杂度为O(V²)。voidgraphDijkstra(Graph*g,intstartIndex,int*dist,int*prev){bool*visited(bool*)calloc(g-vertexCount,sizeof(bool));// 初始化for(inti0;ig-vertexCount;i){dist[i]INT_MAX;prev[i]-1;}dist[startIndex]0;for(inti0;ig-vertexCount;i){// 选择未访问的最小距离顶点intminDistINT_MAX,u-1;for(intj0;jg-vertexCount;j){if(!visited[j]dist[j]minDist){minDistdist[j];uj;}}if(u-1)break;// 剩余顶点不可达visited[u]true;// 松弛操作EdgeNode*edgeg-vertices[u].firstEdge;while(edge){intvedge-dest;if(!visited[v]dist[u]!INT_MAXdist[u]edge-weightdist[v]){dist[v]dist[u]edge-weight;prev[v]u;// 记录前驱节点}edgeedge-next;}}}4.2 路径回溯通过prev数组记录的前驱信息可以重构最短路径// 从终点反向追踪至起点intpath[10],pathLen0;intcurrtarget;while(curr!-1){path[pathLen]curr;currprev[curr];}// 逆序输出即为正向路径for(intjpathLen-1;j0;j--){printf(%d ,path[j]);}五、测试验证测试用例设计涵盖无向图、有向带权图两种场景验证内容包括顶点与边的增删操作DFS与BFS遍历的正确性Dijkstra算法最短路径计算测试输出示例【有向带权图测试】 图结构 (有向图, 5个顶点): 顶点[0](数据0): - [2](权重5) - [1](权重10) 顶点[1](数据1): - [3](权重1) - [2](权重2) 顶点[2](数据2): - [4](权重2) - [3](权重9) - [1](权重3) 顶点[3](数据3): - [4](权重4) 顶点[4](数据4): - [3](权重6) 从顶点0到各顶点的最短路径: 到顶点[0]: 距离0, 路径0 到顶点[1]: 距离8, 路径0 2 1 到顶点[2]: 距离5, 路径0 2 到顶点[3]: 距离9, 路径0 2 1 3 到顶点[4]: 距离7, 路径0 2 4从结果可见Dijkstra算法正确计算了从顶点0到其余各顶点的最短距离及路径。值得注意的是到顶点1的最短路径并非直接边权重10而是经由顶点2中转538算法正确识别了这一更优路径。六、总结本文介绍的图实现具备以下特点存储效率邻接表结构适用于稀疏图场景空间复杂度为O(V E)功能完整支持有向/无向、带权/非带权图提供增删改查全套操作算法覆盖实现了DFS、BFS两种遍历算法以及Dijkstra最短路径算法后续可扩展的方向包括使用优先队列优化Dijkstra算法至O((VE)logV)、增加拓扑排序、强连通分量检测等进阶算法。⚠️源码地址https://github.com/anjuxi/C-graph
【附C源码】基于邻接表的图结构实现与算法实践
发布时间：2026/5/16 15:30:08
【附C源码】基于邻接表的图结构实现与算法实践图Graph作为非线性数据结构的核心成员在社交网络分析、路径规划、依赖管理等领域有着广泛应用。本文将介绍一种基于邻接表的图结构C语言实现涵盖基础操作、遍历算法以及最短路径求解。一、存储结构设计邻接表是图的一种链式存储结构由顶点数组和边链表组成。对于稀疏图而言相较于邻接矩阵邻接表能够显著降低空间复杂度。1.1 数据结构定义// 边节点typedefstructEdgeNode{intdest;// 目标顶点索引intweight;// 边权重structEdgeNode*next;// 下一条边}EdgeNode;// 顶点节点typedefstructVertex{intdata;// 顶点数据EdgeNode*firstEdge;// 邻接边链表头指针}Vertex;// 图结构typedefstruct{Vertex*vertices;// 顶点数组intvertexCount;// 当前顶点数intcapacity;// 容量上限bool isDirected;// 有向/无向标识}Graph;上述设计中EdgeNode采用头插法构建链表这使得边插入操作的时间复杂度为O(1)。isDirected字段用于区分有向图与无向图后者在添加边时需要同时维护双向关系。1.2 内存布局示意Vertex1Vertex0Graphvertices指针Vertex数组vertexCountcapacityisDirecteddata0EdgeNodedest1weight10EdgeNodedest2weight5NULLdata1EdgeNodedest2weight2NULL二、核心操作实现2.1 图的创建与销毁图的初始化需要分配顶点数组空间并将各顶点的边链表置空Graph*graphCreate(intcapacity,bool isDirected){Graph*g(Graph*)malloc(sizeof(Graph));g-vertices(Vertex*)malloc(sizeof(Vertex)*capacity);for(inti0;icapacity;i){g-vertices[i].firstEdgeNULL;}g-vertexCount0;g-capacitycapacity;g-isDirectedisDirected;returng;}销毁操作需遍历所有顶点释放其边链表节点最后释放顶点数组和图结构本身。此处需注意避免内存泄漏尤其是边节点的逐个释放。2.2 边的添加与删除无向图的边添加需要维护两个方向的链接boolgraphAddEdge(Graph*g,intfrom,intto,intweight){// 创建正向边EdgeNode*newEdge(EdgeNode*)malloc(sizeof(EdgeNode));newEdge-destto;newEdge-weightweight;newEdge-nextg-vertices[from].firstEdge;g-vertices[from].firstEdgenewEdge;// 无向图需添加反向边if(!g-isDirected){EdgeNode*reverseEdge(EdgeNode*)malloc(sizeof(EdgeNode));reverseEdge-destfrom;reverseEdge-weightweight;reverseEdge-nextg-vertices[to].firstEdge;g-vertices[to].firstEdgereverseEdge;}returntrue;}边删除操作相对复杂需要遍历链表定位目标节点并正确处理头节点的特殊情况。无向图的边删除同样需要双向处理。2.3 顶点删除顶点删除是图操作中最复杂的部分涉及以下步骤删除该顶点的所有出边遍历其他顶点删除指向该顶点的入边调整受影响的边目标索引因为顶点数组发生移动压缩顶点数组是否是否开始删除顶点v删除v的所有出边遍历其他顶点存在指向v的边?删除该边目标索引v?目标索引减1继续遍历顶点数组前移vertexCount减1该操作的时间复杂度为O(V E)其中V为顶点数E为边数。三、图遍历算法3.1 深度优先搜索DFSDFS采用递归实现沿着一条路径尽可能深入直至无法继续后回溯voidgraphDFSHelper(Graph*g,intindex,bool*visited){visited[index]true;printf(%d ,g-vertices[index].data);EdgeNode*edgeg-vertices[index].firstEdge;while(edge){if(!visited[edge-dest]){graphDFSHelper(g,edge-dest,visited);}edgeedge-next;}}DFS的时间复杂度为O(V E)空间复杂度取决于递归深度最坏情况下为O(V)。3.2 广度优先搜索BFSBFS借助队列实现按层次遍历图的节点voidgraphBFS(Graph*g,intstartIndex){bool*visited(bool*)calloc(g-vertexCount,sizeof(bool));Queue*qqueueCreate(g-vertexCount1);visited[startIndex]true;queueEnqueue(q,startIndex);while(!queueIsEmpty(q)){intindex;queueDequeue(q,index);printf(%d ,g-vertices[index].data);// 将未访问的邻接顶点入队EdgeNode*edgeg-vertices[index].firstEdge;while(edge){if(!visited[edge-dest]){visited[edge-dest]true;queueEnqueue(q,edge-dest);}edgeedge-next;}}}BFS同样具有O(V E)的时间复杂度但空间复杂度为O(V)用于维护队列和访问标记数组。四、最短路径算法4.1 Dijkstra算法实现Dijkstra算法用于求解单源最短路径要求图中不存在负权边。本实现采用简单数组选择最小距离顶点时间复杂度为O(V²)。voidgraphDijkstra(Graph*g,intstartIndex,int*dist,int*prev){bool*visited(bool*)calloc(g-vertexCount,sizeof(bool));// 初始化for(inti0;ig-vertexCount;i){dist[i]INT_MAX;prev[i]-1;}dist[startIndex]0;for(inti0;ig-vertexCount;i){// 选择未访问的最小距离顶点intminDistINT_MAX,u-1;for(intj0;jg-vertexCount;j){if(!visited[j]dist[j]minDist){minDistdist[j];uj;}}if(u-1)break;// 剩余顶点不可达visited[u]true;// 松弛操作EdgeNode*edgeg-vertices[u].firstEdge;while(edge){intvedge-dest;if(!visited[v]dist[u]!INT_MAXdist[u]edge-weightdist[v]){dist[v]dist[u]edge-weight;prev[v]u;// 记录前驱节点}edgeedge-next;}}}4.2 路径回溯通过prev数组记录的前驱信息可以重构最短路径// 从终点反向追踪至起点intpath[10],pathLen0;intcurrtarget;while(curr!-1){path[pathLen]curr;currprev[curr];}// 逆序输出即为正向路径for(intjpathLen-1;j0;j--){printf(%d ,path[j]);}五、测试验证测试用例设计涵盖无向图、有向带权图两种场景验证内容包括顶点与边的增删操作DFS与BFS遍历的正确性Dijkstra算法最短路径计算测试输出示例【有向带权图测试】 图结构 (有向图, 5个顶点): 顶点[0](数据0): - [2](权重5) - [1](权重10) 顶点[1](数据1): - [3](权重1) - [2](权重2) 顶点[2](数据2): - [4](权重2) - [3](权重9) - [1](权重3) 顶点[3](数据3): - [4](权重4) 顶点[4](数据4): - [3](权重6) 从顶点0到各顶点的最短路径: 到顶点[0]: 距离0, 路径0 到顶点[1]: 距离8, 路径0 2 1 到顶点[2]: 距离5, 路径0 2 到顶点[3]: 距离9, 路径0 2 1 3 到顶点[4]: 距离7, 路径0 2 4从结果可见Dijkstra算法正确计算了从顶点0到其余各顶点的最短距离及路径。值得注意的是到顶点1的最短路径并非直接边权重10而是经由顶点2中转538算法正确识别了这一更优路径。六、总结本文介绍的图实现具备以下特点存储效率邻接表结构适用于稀疏图场景空间复杂度为O(V E)功能完整支持有向/无向、带权/非带权图提供增删改查全套操作算法覆盖实现了DFS、BFS两种遍历算法以及Dijkstra最短路径算法后续可扩展的方向包括使用优先队列优化Dijkstra算法至O((VE)logV)、增加拓扑排序、强连通分量检测等进阶算法。⚠️源码地址https://github.com/anjuxi/C-graph
