数据结构|图论：从数据结构到工程实践的核心引擎

Ne0inhk

23 Mar 2026 — 9 min read

个人主页-爱因斯晨

文章专栏-数据结构

作为数据结构中的 “复杂关系建模大师”，图论是解决路径规划、网络分析、依赖调度等问题的核心工具。不同于线性表的 “一对一” 和树的 “一对多”，图的 “多对多” 关系建模能力，使其成为互联网、嵌入式等领域的底层支撑技术。本文将从图的本质出发，用 C 语言手把手实现核心结构与算法，拆解工程落地中的关键细节。

一、图的本质：为何 C 语言实现需先选对存储方式？

图由顶点集（V） 和边集（E） 构成，记为 G=(V,E)。但在 C 语言中，没有原生的 “图” 类型，选择合适的存储结构直接决定了算法效率。实际开发中最常用的两种实现各有侧重：

1. 邻接矩阵：稠密图的 “数组方案”

邻接矩阵用二维数组graph[V][V]存储边关系，graph[i][j]表示顶点 i 到 j 的边权（无向图对称，有向图不对称）。其优势是访问边的时间复杂度为 O (1)，适合顶点数固定、边密集的场景（如电路网络）。

C 语言实现模板如下：

#defineMAX_V1000// 顶点最大数量typedefstruct{int vertex_count;// 实际顶点数int edge_count;// 实际边数int weight[MAX_V][MAX_V];// 边权矩阵，-1表示无直接边} AdjMatrixGraph;// 初始化邻接矩阵voidinit_matrix_graph(AdjMatrixGraph *g,int v_count){ g->vertex_count = v_count; g->edge_count =0;// 初始化边权为-1（无直接边）for(int i =0; i < v_count; i++){for(int j =0; j < v_count; j++){ g->weight[i][j]=-1;} g->weight[i][i]=0;// 顶点到自身权值为0}}// 添加有向边voidadd_directed_edge(AdjMatrixGraph *g,int from,int to,int w){if(from <0|| from >= g->vertex_count || to <0|| to >= g->vertex_count){printf("顶点索引越界\n");return;} g->weight[from][to]= w; g->edge_count++;}

但邻接矩阵的空间复杂度为 O (V²)，当顶点数达到 10000 时，仅存储边权就需要 400MB 内存（int 类型），嵌入式等资源受限场景需谨慎使用。

2. 邻接表：稀疏图的 “链表方案”

邻接表为每个顶点维护一个链表，存储其所有邻接顶点及边权，空间复杂度降至 O (V+E)，是互联网等稀疏图场景的首选（如社交网络中，用户数远大于好友数）。

C 语言实现需注意链表节点的动态内存管理：

// 邻接表节点typedefstructEdgeNode{int to_vertex;// 目标顶点int weight;// 边权structEdgeNode*next;// 下一个邻接顶点} EdgeNode;// 邻接表图结构typedefstruct{int vertex_count;int edge_count; EdgeNode **adj_list;// 指针数组，每个元素指向顶点的邻接链表} AdjListGraph;// 初始化邻接表voidinit_list_graph(AdjListGraph *g,int v_count){ g->vertex_count = v_count; g->edge_count =0; g->adj_list =(EdgeNode **)malloc(v_count *sizeof(EdgeNode *));// 初始化为空链表for(int i =0; i < v_count; i++){ g->adj_list[i]=NULL;}}// 添加无向边（双向添加）voidadd_undirected_edge(AdjListGraph *g,int v1,int v2,int w){if(v1 <0|| v1 >= g->vertex_count || v2 <0|| v2 >= g->vertex_count){printf("顶点索引越界\n");return;}// 向v1的邻接表添加v2 EdgeNode *node1 =(EdgeNode *)malloc(sizeof(EdgeNode)); node1->to_vertex = v2; node1->weight = w; node1->next = g->adj_list[v1];// 头插法（效率更高） g->adj_list[v1]= node1;// 向v2的邻接表添加v1（无向图特性） EdgeNode *node2 =(EdgeNode *)malloc(sizeof(EdgeNode)); node2->to_vertex = v1; node2->weight = w; node2->next = g->adj_list[v2]; g->adj_list[v2]= node2; g->edge_count++;}// 释放邻接表内存（避免内存泄漏）voidfree_list_graph(AdjListGraph *g){for(int i =0; i < g->vertex_count; i++){ EdgeNode *cur = g->adj_list[i];while(cur !=NULL){ EdgeNode *temp = cur; cur = cur->next;free(temp);}}free(g->adj_list); g->vertex_count =0; g->edge_count =0;}

工程实践中，邻接表的 “头插法” 比尾插法更高效，但需注意遍历顺序与插入顺序相反；同时必须实现内存释放函数，避免长期运行导致内存泄漏。

二、核心算法：C 语言落地图论经典问题

图论算法的灵魂是 “遍历与路径”，以下用 C 语言实现两个最具代表性的算法，覆盖无权重和有权重图的核心场景。

1. BFS：无权图的最短路径算法

广度优先搜索（BFS）依赖队列实现，适合求解 “无权图最短路径”（如社交网络的好友推荐、迷宫最短出口）。其核心思想是 “由近及远” 遍历，首次访问顶点时的路径即为最短路径。

基于邻接表的 BFS 实现：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#defineQUEUE_SIZE1000// 循环队列（避免递归栈溢出）typedefstruct{int data[QUEUE_SIZE];int front;int rear;} Queue;voidinit_queue(Queue *q){ q->front =0; q->rear =0;}voidenqueue(Queue *q,int value){if((q->rear +1)% QUEUE_SIZE == q->front){printf("队列满\n");return;} q->data[q->rear]= value; q->rear =(q->rear +1)% QUEUE_SIZE;}intdequeue(Queue *q){if(q->front == q->rear){printf("队列为空\n");return-1;}int value = q->data[q->front]; q->front =(q->front +1)% QUEUE_SIZE;return value;}// BFS求起点到各顶点的最短距离voidbfs_shortest_path(AdjListGraph *g,int start,int*distance){ bool visited[MAX_V]={false}; Queue q;init_queue(&q);// 初始化起点 visited[start]= true; distance[start]=0;enqueue(&q, start);while(q.front != q.rear){int cur =dequeue(&q);// 遍历当前顶点的所有邻接顶点 EdgeNode *node = g->adj_list[cur];while(node !=NULL){if(!visited[node->to_vertex]){ visited[node->to_vertex]= true; distance[node->to_vertex]= distance[cur]+1;// 距离+1enqueue(&q, node->to_vertex);} node = node->next;}}}// 测试：无向无权图的最短路径intmain(){ AdjListGraph g;init_list_graph(&g,5);// 5个顶点（0-4）add_undirected_edge(&g,0,1,1);add_undirected_edge(&g,0,2,1);add_undirected_edge(&g,1,3,1);add_undirected_edge(&g,2,3,1);add_undirected_edge(&g,3,4,1);int distance[MAX_V];for(int i =0; i <5; i++) distance[i]=-1;bfs_shortest_path(&g,0, distance);// 输出0到各顶点的最短距离for(int i =0; i <5; i++){printf("0到%d的最短距离：%d\n", i, distance[i]);}free_list_graph(&g);return0;}

运行结果显示 “0 到 4 的最短距离为 2”，符合实际路径（0→1→3→4 或 0→2→3→4 均为 3 步？此处修正：实际距离应为 3，代码正确但描述笔误，工程中需注意输出校验）。BFS 的关键是避免递归 —— 用循环队列实现可处理大规模顶点，避免栈溢出。

2. Dijkstra：带正权图的最短路径算法

当图存在正权重边时（如交通路网的距离 / 时间），Dijkstra 算法是工业界首选。其核心是 “贪心策略”：每次选择距离起点最近的未访问顶点，更新其邻接顶点的距离。

基于邻接矩阵的 Dijkstra 实现（适合顶点数较少的场景）：

// Dijkstra算法：求起点到各顶点的最短路径（边权为正）voiddijkstra(AdjMatrixGraph *g,int start,int*distance,int*prev){ bool visited[MAX_V]={false};int v_count = g->vertex_count;// 初始化距离数组和前驱数组for(int i =0; i < v_count; i++){ distance[i]= g->weight[start][i]; prev[i]=(distance[i]!=-1)? start :-1;// 前驱顶点} visited[start]= true; distance[start]=0;// 迭代n-1次（除起点外的所有顶点）for(int i =1; i < v_count; i++){// 1. 找未访问顶点中距离起点最近的顶点int min_dist = INT_MAX;int min_vertex =-1;for(int j =0; j < v_count; j++){if(!visited[j]&& distance[j]!=-1&& distance[j]< min_dist){ min_dist = distance[j]; min_vertex = j;}}if(min_vertex ==-1)break;// 剩余顶点不可达 visited[min_vertex]= true;// 2. 松弛操作：更新邻接顶点的距离for(int j =0; j < v_count; j++){if(!visited[j]&& g->weight[min_vertex][j]!=-1){int new_dist = distance[min_vertex]+ g->weight[min_vertex][j];if(distance[j]==-1|| new_dist < distance[j]){ distance[j]= new_dist; prev[j]= min_vertex;}}}}}// 回溯打印最短路径voidprint_path(int prev[],int end){if(prev[end]==-1){printf("%d ", end);return;}print_path(prev, prev[end]);printf("→ %d ", end);}

工程中需注意两点：一是INT_MAX可能导致加法溢出，实际开发可改用long long类型；二是邻接表实现 Dijkstra 时，需搭配优先队列（堆）优化，将时间复杂度从 O (V²) 降至 O ((V+E) logV)，适配大规模图场景。

三、工程避坑：C 语言实现图论的 3 个关键细节

顶点编号与实际数据的映射：工业场景中顶点常是字符串（如 IP 地址、用户名），需用哈希表（如 C 语言的 uthash 库）建立 “字符串→整数编号” 的映射，再传入图算法处理。
负权边的处理边界：Dijkstra 算法无法处理负权边，若需支持负权（如金融交易中的盈亏），需改用 Bellman-Ford 算法，但要注意检测负权回路（可能导致距离无限小）。
大规模图的内存优化：当顶点数超 10 万时，邻接表的指针数组会占用大量内存，可改用 “变长数组 + 文件映射” 方案，将部分数据存储在磁盘，按需加载。

四、总结：图论的工程价值与进阶方向

图论不是 “纸上谈兵” 的理论，而是解决复杂关系问题的 “工程利器”—— 百度地图的路径规划依赖 Dijkstra 变体，美团的骑手调度用图建模订单与骑手的匹配，芯片设计的布线问题本质是图的连通性分析。

用 C 语言实现图论算法时，核心是 “选对存储结构 + 控制内存与效率”：稠密图选邻接矩阵，稀疏图用邻接表；小规模用数组队列，大规模靠堆优化。后续可深入研究拓扑排序（依赖调度）、最小生成树（网络布线）等算法，结合具体业务场景落地，真正发挥图论的核心价值。