当前位置：首页 > news >正文

【附C源码】基于邻接表的图结构实现与算法实践

news 2026/5/16 15:47:10

【附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 内存布局示意

二、核心操作实现

2.1 图的创建与销毁

图的初始化需要分配顶点数组空间，并将各顶点的边链表置空：

Graph*graphCreate(intcapacity,bool isDirected){Graph*g=(Graph*)malloc(sizeof(Graph));g->vertices=(Vertex*)malloc(sizeof(Vertex)*capacity);for(inti=0;i<capacity;i++){g->vertices[i].firstEdge=NULL;}g->vertexCount=0;g->capacity=capacity;g->isDirected=isDirected;returng;}

销毁操作需遍历所有顶点，释放其边链表节点，最后释放顶点数组和图结构本身。此处需注意避免内存泄漏，尤其是边节点的逐个释放。

2.2 边的添加与删除

无向图的边添加需要维护两个方向的链接：

boolgraphAddEdge(Graph*g,intfrom,intto,intweight){// 创建正向边EdgeNode*newEdge=(EdgeNode*)malloc(sizeof(EdgeNode));newEdge->dest=to;newEdge->weight=weight;newEdge->next=g->vertices[from].firstEdge;g->vertices[from].firstEdge=newEdge;// 无向图需添加反向边if(!g->isDirected){EdgeNode*reverseEdge=(EdgeNode*)malloc(sizeof(EdgeNode));reverseEdge->dest=from;reverseEdge->weight=weight;reverseEdge->next=g->vertices[to].firstEdge;g->vertices[to].firstEdge=reverseEdge;}returntrue;}

边删除操作相对复杂，需要遍历链表定位目标节点，并正确处理头节点的特殊情况。无向图的边删除同样需要双向处理。

2.3 顶点删除

顶点删除是图操作中最复杂的部分，涉及以下步骤：

删除该顶点的所有出边
遍历其他顶点，删除指向该顶点的入边
调整受影响的边目标索引（因为顶点数组发生移动）
压缩顶点数组

该操作的时间复杂度为O(V + E)，其中V为顶点数，E为边数。

三、图遍历算法

3.1 深度优先搜索（DFS）

DFS采用递归实现，沿着一条路径尽可能深入，直至无法继续后回溯：

voidgraphDFSHelper(Graph*g,intindex,bool*visited){visited[index]=true;printf("%d ",g->vertices[index].data);EdgeNode*edge=g->vertices[index].firstEdge;while(edge){if(!visited[edge->dest]){graphDFSHelper(g,edge->dest,visited);}edge=edge->next;}}

DFS的时间复杂度为O(V + E)，空间复杂度取决于递归深度，最坏情况下为O(V)。

3.2 广度优先搜索（BFS）

BFS借助队列实现，按层次遍历图的节点：

voidgraphBFS(Graph*g,intstartIndex){bool*visited=(bool*)calloc(g->vertexCount,sizeof(bool));Queue*q=queueCreate(g->vertexCount+1);visited[startIndex]=true;queueEnqueue(q,startIndex);while(!queueIsEmpty(q)){intindex;queueDequeue(q,&index);printf("%d ",g->vertices[index].data);// 将未访问的邻接顶点入队EdgeNode*edge=g->vertices[index].firstEdge;while(edge){if(!visited[edge->dest]){visited[edge->dest]=true;queueEnqueue(q,edge->dest);}edge=edge->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(inti=0;i<g->vertexCount;i++){dist[i]=INT_MAX;prev[i]=-1;}dist[startIndex]=0;for(inti=0;i<g->vertexCount;i++){// 选择未访问的最小距离顶点intminDist=INT_MAX,u=-1;for(intj=0;j<g->vertexCount;j++){if(!visited[j]&&dist[j]<minDist){minDist=dist[j];u=j;}}if(u==-1)break;// 剩余顶点不可达visited[u]=true;// 松弛操作EdgeNode*edge=g->vertices[u].firstEdge;while(edge){intv=edge->dest;if(!visited[v]&&dist[u]!=INT_MAX&&dist[u]+edge->weight<dist[v]){dist[v]=dist[u]+edge->weight;prev[v]=u;// 记录前驱节点}edge=edge->next;}}}

4.2 路径回溯

通过prev数组记录的前驱信息，可以重构最短路径：

// 从终点反向追踪至起点intpath[10],pathLen=0;intcurr=target;while(curr!=-1){path[pathLen++]=curr;curr=prev[curr];}// 逆序输出即为正向路径for(intj=pathLen-1;j>=0;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中转（5+3=8），算法正确识别了这一更优路径。