直接从一个真实场景说起面试手撕图的题目十个人里有八个第一反应是邻接矩阵写出来的代码倒是简单可等面试官追问“节点数量到十万级别还跑得动吗”基本都会卡住。考试里更常见给你一个图让你写出邻接表存储的完整代码或者让你分析“稀疏图下为什么邻接表比邻接矩阵有优势”。实际上邻接表不是某一门课里的偏僻知识点它是图论算法落地的底盘从Dijkstra最短路径到拓扑排序从网络流建模到社交关系分析底层都离不开这张“表”。这篇文章不搞理论复读直接围绕“图的邻接表存储完整代码”展开把结构定义、初始化、建图、遍历、算法适配、内存管理这些全部串起来。目标是让你看完之后能够独立写出一份能跑、能改、能应对面试追问的邻接表实现而不是只会背个结构体定义。适合三类人看正在复习数据结构期末考的学生、准备算法面试的开发者、以及需要用图建模但不想引第三方库的工程实践者。前两类需要的是完整可复现的代码和考点解析后一类更需要的是工程化写法——比如邻接表怎么处理动态扩容、怎么释放内存、怎么适配不同图类型。这篇文章都会覆盖到。1. 邻接表到底在解决什么问题为什么非它不可1.1 邻接矩阵的痛点空间换时间的代价在稀疏图里是灾难先花点篇幅把“为什么是邻接表”这件事说透。图存储最直觉的思路就是邻接矩阵开一个 N×N 的二维数组matrix[i][j] 1表示 i 到 j 有一条边。查找任意两点之间是否有边时间复杂度 O(1)写起来也简单到闭着眼睛都能敲。但这个方案的致命问题在于空间。N 个顶点的图邻接矩阵需要 N² 个存储单元。对于稠密图——比如每个节点都和大部分其他节点相连——N² 的代价是合理的因为矩阵里绝大多数位置都存的是有效信息。可现实世界里的图绝大多数是稀疏图社交网络上一个人平均认识几百个好友但全网可能有几亿用户一个网页平均链接到几十个其他页面但整个互联网有百亿级页面。这种场景下邻接矩阵里 99% 以上的位置存的都是无意义的 0。用具体数字说话。假设图有 10 万个顶点平均每个顶点的出度是 10。邻接矩阵要开 10万 × 10万 的数组按每个元素 1 字节算需要约 10GB。而真实的边只有 10万 × 10 100万条。邻接表呢顶点数组占 10万 × sizeof(头节点)边节点占 100万 × sizeof(边节点)算下来一般也就几十MB 到一两百MB差了不止一个数量级。所以结论很简单稀疏图选邻接表稠密图选邻接矩阵。判断标准就是看边数 E 和顶点数 V 的关系。如果 E 接近 V² 的上限邻接矩阵的空间优势还能靠 O(1) 查询弥补如果 E 远小于 V²邻接表就是唯一合理的选择。1.2 邻接表的存储模型顶点数组 边链表怎么组织才清晰邻接表的本质我自己习惯把它理解成“每个人一张朋友名单”。你有 N 个朋友你的桌上就有一张写着你朋友名字的纸条张三也有自己的一张纸条。要把所有人的朋友关系整理出来只需要把 N 张纸条按编号顺序排好这就成了邻接表。落到代码层面这个模型由两部分组成顶点表一个数组数组下标就是顶点编号每个数组元素是一个“头节点”它包含顶点数据和一条链表的头指针。边链表每个顶点的头指针指向一条链表链表中的每个节点代表一条从该顶点出发的边节点里存的是这条边指向的邻居顶点编号。这个模型的内存布局比邻接矩阵“碎”但换来的是只存储真实存在的边。空间复杂度从 O(V²) 降到 O(V E)对稀疏图是革命性的。代价是查询“u 和 v 是否相邻”不能 O(1) 完成得顺着 u 的链表遍历一遍最坏情况是 O(出度)。这个取舍在工程上完全可接受因为大多数图算法的瓶颈本来就不在单次边查询上。还有一个细节容易踩坑网上的代码和教材里边链表的方向到底是谁指向谁编码风格差异很大。主流有两种出边表每个顶点存的是“从它出发能到达哪些节点”适合遍历出边、做DFS/BFS、算最短路径。入边表也叫逆邻接表每个顶点存的是“有哪些节点指向它”适合做拓扑排序中的入度统计、反向图遍历。最高效的工程做法不是二选一而是建图时同时维护出边表和入边表代价是每个边节点要存两处但很多算法比如Kosaraju求强连通分量就需要两个方向都跑。后面代码示例里我会给一个支持这种需求的实现。2. 完整代码拆解从结构体定义到建图每个字段都有讲究2.1 结构体定义的标准写法与扩展思路来看一份完整的、可以直接编译运行的邻接表实现。先看结构体定义部分。#include stdio.h #include stdlib.h #include string.h // 边表节点代表一条从某个顶点出发的边 typedef struct EdgeNode { int adjvex; // 该边指向的顶点编号 int weight; // 边的权值无权图填0或1 struct EdgeNode *next; // 指向下一条边 } EdgeNode; // 顶点表节点每个顶点对应一个链表头 typedef struct VertexNode { int data; // 顶点数据可以是编号、名称或业务ID int inDegree; // 入度用于拓扑排序可选字段 EdgeNode *firstEdge; // 指向第一条边 } VertexNode; // 图结构顶点数组 顶点数 边数 typedef struct { VertexNode *vertices; // 动态数组大小 vertexNum int vertexNum; int edgeNum; int directed; // 1表示有向图0表示无向图 } Graph;这段代码里有几个字段值得细说。先看adjvex和weight。adjvex是必填字段它决定这条边连向谁。weight看场景如果是带权图比如城市间公路里程、网络拓扑里的链路时延这个字段就得存实际权值如果是无权图统一置 1 即可这样在统计路径长度时就不需要额外判断。再看inDegree。这个字段很多人一开始不理解为什么要存在顶点节点里。拓扑排序算法里最直观的做法是“每次找一个入度为0的顶点删掉它的所有出边”删出边就会影响邻居的入度。如果入度要现算每次都得遍历全图复杂度直接飙到 O(V·E)。把入度作为顶点表的字段维护每次删边时同步更新拓扑排序就能做到 O(VE)。这是一个“用空间预计算换取算法效率”的典型例子。还有directed字段。无向图的每条边要在两个方向各插入一次有向图只插入一次。建图函数里根据这个标志决定插入逻辑。有些实现把这个标志放建图函数外面由调用方自己判断也行但放进图结构的好处是图自己“记得”自己的类型后续写打印、遍历、算法函数时直接查就行不用到处传参数。2.2 初始化、建图、打印三条核心函数的完整逻辑初始化函数负责把顶点数组建好把所有链表头置空。这里的核心问题是不能只开辟空间必须逐个初始化。用malloc分配完数组后内存里的内容是随机的里面的firstEdge指针是个野指针直接拿来当空指针判断会出大问题。所以我习惯写一个initGraph把每个顶点的firstEdge置为NULL、inDegree置为 0。// 初始化图vertexNum个顶点顶点数据默认为0~N-1 Graph* initGraph(int vertexNum, int directed) { Graph *g (Graph*)malloc(sizeof(Graph)); if (!g) return NULL; g-vertexNum vertexNum; g-edgeNum 0; g-directed directed; g-vertices (VertexNode*)malloc(sizeof(VertexNode) * vertexNum); if (!g-vertices) { free(g); return NULL; } for (int i 0; i vertexNum; i) { g-vertices[i].data i; g-vertices[i].inDegree 0; g-vertices[i].firstEdge NULL; } return g; }注意这里我让顶点数据默认等于编号。工程场景下顶点数据可能是一个结构体名字、坐标、业务属性那就把int data换成一个结构体字段并另写数据加载函数。学习阶段用编号最直观。加边函数是邻接表的灵魂。它的核心操作是“头插法”——新边节点插到链表头部。为什么不用尾插法最直接的原因是头插法不需要遍历链表找尾节点时间复杂度 O(1)。但头插法的副作用是遍历出来的邻接顺序是逆序的你按 (0,1)、(0,2) 的顺序加边打印时 1 号顶点的链表会先输出 2 再输出 1。这个不影响任何算法正确性但面试时如果要求输出某个顺序就要注意这个细节。// 添加一条边u为起点v为终点w为权值 void addEdge(Graph *g, int u, int v, int w) { // 插入到u的链表头部 EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex v; e-weight w; e-next g-vertices[u].firstEdge; g-vertices[u].firstEdge e; // 无向图需要反向再插一次 if (!g-directed) { EdgeNode *re (EdgeNode*)malloc(sizeof(EdgeNode)); re-adjvex u; re-weight w; re-next g-vertices[v].firstEdge; g-vertices[v].firstEdge re; g-edgeNum; } g-edgeNum; }无向图情况下edgeNum要加两次这地方特别容易写错。有些教材里edgeNum的定义是“边数”无向图一条边算一条那就应该只在有向图分支里加、或者每加两条才加一口。我这种定义按“实际插入的链表项数”来累计写打印或做复杂度分析的时候心里要有个换算关系。建议代码注释里写清楚这个约定不然后续维护会晕。打印图函数纯粹是检验建图是否正确的工具但它的价值很高——每次写完建图代码第一步就是打印整个邻接表逐个顶点检查链表内容是否符合预期。我见过很多人跳过这一步直接去写遍历算法结果遍历结果完全不对回头查建图建错了浪费大量时间。void printGraph(Graph *g) { for (int i 0; i g-vertexNum; i) { printf([%d] (in:%d):, i, g-vertices[i].inDegree); EdgeNode *p g-vertices[i].firstEdge; while (p) { printf( - %d, p-adjvex); if (g-directed p-weight 0) { printf((w:%d), p-weight); } p p-next; } printf( - NULL\n); } }打印时把入度也打出来因为入度字段经常是算法调试的关键线索。实际开发里我会再加一个“按邻接矩阵形式输出”的辅助函数把邻接表临时转换为矩阵打印方便和手工算的结果对照。2.3 完整代码示例一份可直接跑的基准实现把上面的函数组合起来附上一个建图示例和主函数#include stdio.h #include stdlib.h typedef struct EdgeNode { int adjvex; int weight; struct EdgeNode *next; } EdgeNode; typedef struct VertexNode { int data; int inDegree; EdgeNode *firstEdge; } VertexNode; typedef struct { VertexNode *vertices; int vertexNum; int edgeNum; int directed; } Graph; Graph* initGraph(int vertexNum, int directed) { Graph *g (Graph*)malloc(sizeof(Graph)); g-vertexNum vertexNum; g-edgeNum 0; g-directed directed; g-vertices (VertexNode*)malloc(sizeof(VertexNode) * vertexNum); for (int i 0; i vertexNum; i) { g-vertices[i].data i; g-vertices[i].inDegree 0; g-vertices[i].firstEdge NULL; } return g; } void addEdge(Graph *g, int u, int v, int w) { EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex v; e-weight w; e-next g-vertices[u].firstEdge; g-vertices[u].firstEdge e; if (g-directed) { g-vertices[v].inDegree; } else { EdgeNode *re (EdgeNode*)malloc(sizeof(EdgeNode)); re-adjvex u; re-weight w; re-next g-vertices[v].firstEdge; g-vertices[v].firstEdge re; g-edgeNum; } g-edgeNum; } void printGraph(Graph *g) { for (int i 0; i g-vertexNum; i) { printf([%d] (in:%d):, i, g-vertices[i].inDegree); EdgeNode *p g-vertices[i].firstEdge; while (p) { printf( - %d(w:%d), p-adjvex, p-weight); p p-next; } printf( - NULL\n); } } int main() { // 测试用例5个顶点的有向图边为 (0-1) (0-2) (1-3) (2-3) (3-4) Graph *g initGraph(5, 1); addEdge(g, 0, 1, 2); addEdge(g, 0, 2, 3); addEdge(g, 1, 3, 4); addEdge(g, 2, 3, 1); addEdge(g, 3, 4, 2); printGraph(g); return 0; }这里的有向图建图方式同时维护了inDegree后续做拓扑排序可以直接用不需要重新统计。测试用例里特意选了带环和不带环的混合结构便于调试。编译运行命令不需要特别说明gcc直接编译就能过。3. 遍历算法怎么在邻接表上跑DFS 和 BFS 的正确姿势3.1 深度优先遍历递归写法、迭代写法、访问顺序差异图的深度优先遍历DFS在邻接表上实现核心思想跟树的前序遍历一致从某个顶点出发沿着第一条未访问的边深入直到走不动再回溯。只是图里可能有环所以必须有visited数组防止死循环。递归写法最直观也是面试手写最常见的void dfsRecursive(Graph *g, int v, int *visited) { visited[v] 1; printf(visit %d\n, v); EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; if (!visited[neighbor]) { dfsRecursive(g, neighbor, visited); } p p-next; } } void dfsGraph(Graph *g, int start) { int *visited (int*)calloc(g-vertexNum, sizeof(int)); dfsRecursive(g, start, visited); // 非连通图的处理对未访问顶点继续DFS for (int i 0; i g-vertexNum; i) { if (!visited[i]) { dfsRecursive(g, i, visited); } } free(visited); }注意这个写法里visited数组用calloc初始化而不是malloc后手动填充 0。calloc会自动把内存清零省一行代码也少一个犯错机会。非连通图处理那段很多人漏掉如果图不连通从一个起点出发只能访问一个连通分量必须遍历所有顶点对没访问过的继续深搜。递归 DFS 的问题是当图很深时比如一条链状的图顶点数几十万递归调用栈会爆掉。工程上要么显式增大栈空间要么改成迭代写法。迭代写法用栈模拟递归过程void dfsIterative(Graph *g, int start) { int *visited (int*)calloc(g-vertexNum, sizeof(int)); int *stack (int*)malloc(sizeof(int) * g-vertexNum); int top -1; stack[top] start; while (top 0) { int v stack[top--]; if (visited[v]) continue; visited[v] 1; printf(visit %d\n, v); EdgeNode *p g-vertices[v].firstEdge; // 为了保持与递归一致的访问顺序可以逆序入栈 while (p) { if (!visited[p-adjvex]) { stack[top] p-adjvex; } p p-next; } } free(visited); free(stack); }这里有个常见困惑迭代写法和递归写法访问顺序可能不一致。原因在于栈是 LIFO 的邻接表里链表节点的顺序本身又是逆序两个逆序叠加后某些场景下访问顺序和递归版本不同。如果题目要求一个特定的遍历序列需要额外处理入栈顺序。这一点面试时主动提出来反而能体现你真的理解 DFS 的机制而不是背代码。3.2 广度优先遍历队列在邻接表上的天然适配广度优先遍历BFS用队列实现。它的访问顺序是逐层扩散先访问起点然后访问起点的所有邻居再访问邻居的邻居。邻接表的链表结构让“取出一个顶点的所有邻居”变得非常自然直接遍历链表即可。void bfsGraph(Graph *g, int start) { int *visited (int*)calloc(g-vertexNum, sizeof(int)); int *queue (int*)malloc(sizeof(int) * g-vertexNum); int head 0, tail 0; queue[tail] start; visited[start] 1; while (head tail) { int v queue[head]; printf(visit %d\n, v); EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; if (!visited[neighbor]) { visited[neighbor] 1; queue[tail] neighbor; } p p-next; } } free(visited); free(queue); }BFS 里有一个经典坑入队时就要标记 visited不能出队时再标记。如果出队时才标记那么同一个顶点可能被多个邻居重复入队——因为它还没被标记每个邻居遍历时都觉得自己发现了新大陆。在带环图里这会导致队列无限膨胀甚至死循环。这也顺便解释了一个编程习惯状态标记的时机要放在状态进入容器的那一刻而不是弹出那一刻。队列我用数组模拟而不是用链式队列。原因是面试或竞赛环境里数组队列更快、更不容易出内存泄漏问题而且容量开vertexNum就够用了。有人可能问为什么不直接用循环队列BFS 中每个顶点最多入队一次普通数组队列不存在“再次写入同一位置”的情况用循环队列反而是冗余。3.3 遍历顺序依赖链表的插入方式这个细节你迟早要面对前面建图用的是头插法导致每个顶点的邻接链表里的顺序和输入顺序相反。这个顺序会影响 DFS、BFS 以及后面要讲的最短路径算法的实际执行路径——尽管不影响最终正确性但会影响中间过程的输出序列。举例说明。现在输入三条边0→1、0→2、0→3。因为每次都头插vertices[0].firstEdge会先指向 33 再指向 22 再指向 1。所以从 0 开始 DFS第一个访问到的邻居是 3而不是输入顺序里的 1。如果你希望遍历顺序和输入顺序一致有两个办法改用尾插法每次找链表末尾再插入复杂度 O(出度)建图时间从 O(E) 变成 O(V·E) 最坏情况。可以额外维护一个tail数组指向每个链表的尾部把尾插降到 O(1)。保持头插法但在遍历时对邻居先收集后排序这种办法适合需要输出特定序列的场景。我个人的经验是学习阶段用头插法就行面试时如果题目要求按照某种字典序输出遍历结果最稳妥的做法是在遍历当前顶点的邻居前先把邻居节点值收集到一个数组并排序再依次递归。这样不管邻接表内部顺序是怎样的输出总是可预期的。4. 邻接表和经典图算法怎么衔接不止是存下来那么简单4.1 拓扑排序邻接表的入度字段一到位代码立刻就简单了拓扑排序是 DAG有向无环图上的经典算法用邻接表实现时有两个方向Kahn 算法BFS思想和 DFS 变种。Kahn 算法是最常用的它依赖于入度统计。有了前面结构体里的inDegree字段Kahn 算法写起来几乎一气呵成先把所有入度为 0 的顶点入队然后依次弹出顶点把它所有出边的终点入度减 1如果某个终点的入度变成 0再把它放进队列。循环结束后如果弹出的顶点数不等于总顶点数说明图里有环。void topologicalSort(Graph *g) { int *queue (int*)malloc(sizeof(int) * g-vertexNum); int head 0, tail 0; for (int i 0; i g-vertexNum; i) { if (g-vertices[i].inDegree 0) { queue[tail] i; } } int count 0; while (head tail) { int v queue[head]; printf(%d , v); count; EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; g-vertices[neighbor].inDegree--; if (g-vertices[neighbor].inDegree 0) { queue[tail] neighbor; } p p-next; } } if (count ! g-vertexNum) { printf(\n图中有环拓扑排序不完整\n); } free(queue); }这段代码最大的优点是用入度字段直接做增减操作不用每次去算入度。但注意运行完拓扑排序后所有顶点的inDegree都被改成了 0如果之后还要继续使用图比如跑其他算法需要重新初始化入度。我的习惯是在拓扑排序函数的入口处先记录一份入度备份或者干脆重新调用一个recalcInDegree函数。4.2 Dijkstra 最短路径邻接表 优先队列的标准组合打法Dijkstra 算法是邻接表最受益的算法之一。如果用邻接矩阵实现每轮找“当前距离最小的未访问顶点”是 O(V)更新所有邻居是 O(V)总复杂度 O(V²)。用邻接表 优先队列最小堆更新操作只涉及真实存在的边摊还下来复杂度降到 O((VE)logV)。在处理稀疏大图时这个差距是决定性的。关键实现点是优先队列里存的是“顶点编号 当前最短距离”的二元组。每次从堆里弹出距离最小的顶点如果它已经被访问过跳过否则标记访问遍历它的邻接链表试图松弛邻居节点。这里有个经验优先队列里可能会存入同一个顶点的多个不同距离版本因为松弛时发现更短距离就会 push 一次新版本所以弹出时要检查“当前距离是否比 dist 数组里记录的更小”如果不是直接忽略。这个检查我见过很多人漏掉结果算法结果没问题但堆里积压了大量无效项性能退化成灾难。// 简化版不包含完整优先队列实现只展示邻接表上的松弛逻辑 // dist[] 初始为 INF; 用数组模拟的最小堆在完整项目中实现 void dijkstra(Graph *g, int start, int *dist) { // 假设这里有一个最小堆 heap每个元素是 (node, distance) // 初始化 dist[start]0将 (start,0) 入堆 while (!heapEmpty()) { int v heapPopNode(); int d heapPopDist(); if (d dist[v]) continue; // 过期的堆条目 EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; if (dist[v] p-weight dist[neighbor]) { dist[neighbor] dist[v] p-weight; heapPush(neighbor, dist[neighbor]); } p p-next; } } }邻接表在这里的意义是松弛邻居时只需要看当前顶点链表里的节点不会把时间浪费在根本不存在的边上。如果图有 10 万顶点、平均出度 10一次 Dijkstra 的实际比较次数大概在百万级换成邻接矩阵光遍历矩阵就要 10 亿次操作。4.3 并查集和最小生成树邻接表如何配合 Kruskal 与 Prim最小生成树的两种经典算法对图存储有不同的依赖。Kruskal 的核心操作是边排序 并查集判环它根本不需要遍历某个顶点的所有邻居只需要把边抽出来排序。所以很多人用邻接表存完图后还要再构造一个“边数组”交给 Kruskal。这种情况下图的存储格式是邻接表还是边集数组区别不大。Prim 算法就不一样了。常规 Prim 需要反复取“离当前已选顶点集合最近的未选顶点”如果每次都扫描所有顶点复杂度 O(V²)。但在邻接表 优先队列的实现里可以做到类似 Dijkstra 的低复杂度每次把一个顶点加入生成树时遍历它的邻接链表把所有连接未选顶点的边插入堆中。邻接表的稀疏性在这里再次发挥作用。整套链路是这样的建图用邻接表 → 遍历邻接表生成边数组 → Kruskal 排序并查集判环或者邻接表 堆实现 Prim。两种路线你都要会面试官可能会问“为什么 Kruskal 更适合稀疏图”这类问题本质就是在考察你对空间与时间复杂度的理解是否到位。5. 缺陷排查手册邻接表代码最容易出错的 7 个地方5.1 从“段错误”到“逻辑错误”一次实战排查过程记录我自己带人写邻接表时见过最多的报错是段错误。经历过一次印象深刻的排查同学建了一个 6 个顶点的图加完边一打印就段错误。代码逻辑看起来完全没毛病后来用调试器跑发现在addEdge里要写入g-vertices[u].firstEdge但g的顶点数组根本没有正确分配。根源是初始化函数里少了一行分配完vertices数组后没有检查是否分配成功。当顶点数到几十万时malloc失败的概率不是零一旦返回NULL连着的第一次加边就会写空指针。所以所有malloc之后第一件事就是判空这是 C 语言编程的底线习惯。给的代码里初始化函数已经加了判空处理实际项目里还要在addEdge里加一个if (!g) return;之类的防御式判断。第二个典型错误更隐蔽无向图建图时只插了一次边。比如addEdge(g,1,3,5)执行后只有vertices[1]的链表里有 3vertices[3]的链表里找不到 1。这个问题最坑的地方在于单看打印结果好像图还不错只是少了半边真正跑 BFS 或连通分量判断时才完全错乱。排查方法很简单打印图时检查对称性——无向图中如果 i 的链表里有 jj 的链表里必须有 i。第三个错误是重复边导致的计数混乱。同一个测试用例里如果不小心把同一条边加了两次比如从文件读数据时没判重邻接表会多出一个平行边节点。这对大多数算法没影响但会让 Kruskal 的边数量统计出错也让最小生成树的正确性无法保证。解决办法有两个建图时判重遍历当前顶点的链表检查有没有已存在同样邻居或者使用哈希表辅助。竞赛和考试场景里一般默认输入没有重复边但工程代码里一定要处理。5.2 常见问题速查表按症状定位到根因我把平时排查邻接表问题时用到的对照表整理出来每个症状都对应最可能的根因和解决手段症状可能原因解决思路打印时崩溃/段错误顶点数组未初始化、malloc失败未判空检查 initGraph 是否循环初始化 firstEdgemalloc 后判空无向图少了半边边无向分支没写反向插入检查 addEdge 中 directed0 分支遍历结果顺序奇怪头插法导致邻接逆序无需修复理解即可如要求顺序改用尾插或排序BFS 死循环visited 标记位置错误入队时标记visited而不是出队时拓扑排序结果为空/不全inDegree 未初始化或建图时忘更新initGraph 中置0addEdge有向分支更新入度链表中出现重复边建图时未判重加边前遍历链表查重或输入预处理求最短路径结果明显偏大weight 字段忘记赋值addEdge 参数w未传给边节点free 时报堆损坏边节点或顶点数组被重复释放写 destroyGraph 时逐个节点释放避免二次free这张表不是让你背的而是排查时对照着定位。我自己的经验是邻接表的问题九成来自“建立图的过程有问题”而不是“遍历算法有问题”所以每次写完先打印图确认图的结构完全正确再往上叠算法能省出大量排错时间。5.3 内存释放的完整实现漏掉一个 free 就是一次内存泄漏图这种动态结构在长期运行的进程里反复创建和销毁是家常便饭。C 语言没有垃圾回收写一个正确的destroyGraph和写建图一样重要。核心逻辑是先遍历所有顶点的链表逐个free边节点最后free顶点数组和Graph结构体本身。void destroyGraph(Graph *g) { if (!g) return; for (int i 0; i g-vertexNum; i) { EdgeNode *p g-vertices[i].firstEdge; while (p) { EdgeNode *tmp p-next; free(p); p tmp; } } free(g-vertices); free(g); }代码简单但有几个细节要强调。第一保存tmp p-next必须在free(p)之前不然就丢了链表后续节点。第二无向图里每条边被存了两份这两个边节点都要释放上面的循环天然会处理。第三如果建图过程中曾经申请过别的辅助结构比如顶点哈希表、边数组也都要在销毁函数里一起处理。另外提醒一下在异常流程里用goto或集中清理函数是 C 工程的老传统如果初始化过程中途失败前面已经分配的资源不能丢写在统一出口处释放。初学阶段可能觉得多余但在资源受限的嵌入式场景或者长期服务的进程里内存泄漏一次两次还能容忍泄漏上千次就是事故了。6. 邻接表的工程化升级与面试实战指南6.1 超越教材的升级方向动态扩容、顶点哈希映射、多态数据承载教材里的邻接表基本固定为“整数顶点编号 int 数据”但在真实项目里顶点往往不是连续的整数而是字符串ID、对象ID、甚至是浮点数坐标。这时候要用哈希映射把外部顶点ID映射成数组下标 0~N-1邻接表内部继续用整数编号操作外部对象映射表单独维护。另一个常见的工程化需求是动态扩容。上文initGraph要求一开始就知道顶点数。有些场景下顶点数是动态增长的比如流式读入数据此时可以按 2 倍或 1.5 倍扩容顶点数组扩容后所有已有顶点的firstEdge指针都要迁移到新数组。这段逻辑比较繁琐建议封装成ensureCapacity函数而且扩容后要重新分配新数组、逐个复制旧顶点、释放旧数组避免指针悬挂。还有多态数据承载的问题。如果每个顶点要存“城市名 人口 坐标”这类复合信息VertexNode里的int data就要扩展成一个结构体指针或者用void*指向业务数据。C 语言里void*用起来稍显繁琐但换来的是通用性。C 或 Rust 里可以用模板或泛型设计思路一致图结构只负责拓扑关系顶点内容由业务层填充。6.2 面试题目最爱的追问方向和应对模板面试手写邻接表时除了基础代码面试官几乎一定会追问几个方向。我把常见的整理出来“为什么不用邻接矩阵”答稀疏图下空间复杂度从 O(V²) 降到 O(VE)。进一步要能说出“当 E 接近 V² 时邻接矩阵的 O(1) 边查询才值得”这种权衡分析。“遍历过程中怎么避免重复访问”答必须用 visited 数组。追问“为什么树遍历不需要 visited”因为树没有环图可能有环。“如果图特别大内存放不下怎么办”答考虑外部存储 分块加载或者用数据库图存储方案。邻接表本身解决不了超大规模问题需要分布式图计算框架。这一题更多考的是系统设计思维。“如果是从文件里读一个很大的图你会怎么建邻接表”答先读第一行拿顶点数和边数预分配顶点数组然后逐行读边数据每条边addEdge。如果边数特别多还要考虑用缓冲读取而不是scanf逐个读。“你的 addEdge 能处理自环和平行边吗”答自环可以的插入逻辑不排斥 uv平行边也可以插入但某些算法需要额外去重。主动讲出这个问题比被问到时才支支吾吾好得多。我建议你去面试之前把“邻接表 DFS BFS 拓扑排序”这四个代码块手写三遍。第一遍看书写第二遍默写第三遍在白板上画着讲。等你讲的时候能讲清楚“这个inDegree字段为什么而存在”“这个visited为什么入队就要置为1”基础知识基本就稳了。6.3 不同语言实现邻接表的差异C、C、Python、Java 的建模方式如果参加在线笔试或做工程实践语言选择会影响邻接表的具体写法。C 语言最直接用 struct 指针但要自己管内存。C 可以使用vectorint adj[N]或vectorvectorint adj每行就是一条链表插入用push_back省了指针操作。Java 用ArrayListInteger[] adj同样省心。Python 更常见的是直接用字典adj {0: [1,2], 1: [3], 2: [3]}。这其实就是邻接表的动态版。有向图、无向图的区别在于是否双向 append。Python 写图算法调试效率极高但性能和内存控制不如 C。算法竞赛里 C 的邻接表有人喜欢用vectorpairint,int adj[N]存带权图简洁高效强烈推荐。语言可以换但核心思想是通用的顶点数组/容器 每个顶点关联一个邻居列表。把 C 版本的逻辑吃透了换成任何语言都只是语法层面的翻译。这也是为什么我一直建议先学 C 版本邻接表因为它把存储结构、指针操作这些底层细节全部暴露出来让你真正理解“一个顶点怎么找到它的所有邻居”。7. 从一份代码到一套方法论邻接表还能怎么扩展7.1 邻接表到邻接多重表与十字链表了解兄弟方案去理解取舍邻接表不是图存储的唯一结构学习框架里通常还会提到邻接多重表和十字链表。邻接多重表专门处理无向图每条边用一个节点表示同时挂在两个顶点的链表上解决“无向图每条边存两份”的内存浪费和同步更新问题。十字链表则是有向图的进阶方案同时维护出边和入边每条边节点同时处于两个链表中一个从弧尾出发的出边链一个指向弧头的入边链。这些进阶结构原理上不复杂但代码实现比邻接表繁琐得多。我个人建议初学阶段把邻接表吃透就够应付绝大多数考试和面试。碰到“为什么这里用十字链表”这类问题核心逻辑是如果你要频繁遍历反向边比如求强连通分量十字链表能让你同时拥有出边和入边而不需要额外维护两个邻接表。理解到这一层就够了真的让你手写十字链表的机会并不多。7.2 邻接表在后端系统里的真实案例推荐系统、知识图谱、链路追踪邻接表不只是考试题。我做过一个轻量的用户关系分析服务用户数大概几百万每个用户平均关注几十个人用 PostgreSQL 存关系表是可以的但每次做两层关系扩展要频繁 JOIN性能不理想。后来在内存里直接用邻接表Go 语言里用map[int][]int缓存用户关系配合 BFS 做共同关注推荐单机扛住了每秒几百次的查询。另一个典型的邻接表应用是知识图谱的图查询引擎。知识图谱本质是海量带标签的有向图每条三元组就是一条带权边。为了支持“从某个实体出发找它的邻居实体”这种查询底层的索引结构也是邻接表的变体每个实体维护一个关系列表列表项是“关系类型 目标实体”。这类系统叫属性图存储但底层思想仍然是“顶点 邻居列表”。链路追踪系统也大量使用树/图结构表达调用链。一次请求会经过多个服务形成一棵调用树多个请求叠加后就变成一张复杂的调用图。监控面板上画出的图表底层存储往往就是一张邻接表每个服务是顶点每次 RPC 是边需要时从某个入口顶点开始 DFS 或 BFS 展开调用链。这些场景共同说明一件事邻接表不是停留在课本上的玩具凡是遇到“点与点之间有连接关系、且连接数量远小于点对总数”的数据邻接表就是最自然的第一选择。学会在数据结构层面抽象问题比学会某一种语言问法更有长期价值。7.3 从邻接表到图计算框架什么时候你需要抬头看更大的世界邻接表再高效也有限度。当图的规模超过单机内存时比如几十亿顶点、几千亿边的社交关系图你就不能再用“一个数组 一堆链表”的本地模型而要考虑分布式图计算框架。这些框架内部也会用邻接表思想——每个分区存储一批顶点及其出边——但跨机器的通信、数据分区策略、容错机制已经远远超出普通数据结构课程的范畴。学习路径上我建议你在掌握了邻接表之后再看两个方向一是图数据库比如以原生图存储为卖点的产品它的查询本质是“从顶点走邻居”理解邻接表能帮你快速理解索引结构的设计动机二是图算法平台比如批处理或流式的图计算引擎里面 Pregel 模型的“每个顶点接收消息、发送消息”机制也和 BFS 的逐层扩散有精神上的相通。从这个意义上说邻接表是你进入图计算世界的第一个正式入口。它很简单但一点都不肤浅——后续学习诺大图算法至少有一半时间你在做的事情仍然是“放在邻接表上的迭代”。我自己用过邻接表这么多年最深的体会是**图这种结构难点从来不是代码而是建模——你能不能一眼看出一个问题可以用图来表达然后选对一个合适的存储方式让后续算法跑得又快又稳。**邻接表就是这个选型金字塔的底座。把它彻底吃透你会发现在最短路径、拓扑排序、连通分量这些常见问题上你开始有能力自己设计和调试了而不是每一步都得去查别人的模板代码。如果你现在正对着书里的邻接表代码发懵我的建议很简单别只看动手抄一遍抄完加几条边打印出来再删掉打印函数换成 BFS 试试。三遍下来这个数据结构的每一根指针、每一个字段就都长在你脑子里了。 
长河君 · 2026/10/15 22:30:08 · 阅读 1.2k 图邻接表存储完整代码：从结构定义到算法实现
直接从一个真实场景说起面试手撕图的题目十个人里有八个第一反应是邻接矩阵写出来的代码倒是简单可等面试官追问“节点数量到十万级别还跑得动吗”基本都会卡住。考试里更常见给你一个图让你写出邻接表存储的完整代码或者让你分析“稀疏图下为什么邻接表比邻接矩阵有优势”。实际上邻接表不是某一门课里的偏僻知识点它是图论算法落地的底盘从Dijkstra最短路径到拓扑排序从网络流建模到社交关系分析底层都离不开这张“表”。这篇文章不搞理论复读直接围绕“图的邻接表存储完整代码”展开把结构定义、初始化、建图、遍历、算法适配、内存管理这些全部串起来。目标是让你看完之后能够独立写出一份能跑、能改、能应对面试追问的邻接表实现而不是只会背个结构体定义。适合三类人看正在复习数据结构期末考的学生、准备算法面试的开发者、以及需要用图建模但不想引第三方库的工程实践者。前两类需要的是完整可复现的代码和考点解析后一类更需要的是工程化写法——比如邻接表怎么处理动态扩容、怎么释放内存、怎么适配不同图类型。这篇文章都会覆盖到。1. 邻接表到底在解决什么问题为什么非它不可1.1 邻接矩阵的痛点空间换时间的代价在稀疏图里是灾难先花点篇幅把“为什么是邻接表”这件事说透。图存储最直觉的思路就是邻接矩阵开一个 N×N 的二维数组matrix[i][j] 1表示 i 到 j 有一条边。查找任意两点之间是否有边时间复杂度 O(1)写起来也简单到闭着眼睛都能敲。但这个方案的致命问题在于空间。N 个顶点的图邻接矩阵需要 N² 个存储单元。对于稠密图——比如每个节点都和大部分其他节点相连——N² 的代价是合理的因为矩阵里绝大多数位置都存的是有效信息。可现实世界里的图绝大多数是稀疏图社交网络上一个人平均认识几百个好友但全网可能有几亿用户一个网页平均链接到几十个其他页面但整个互联网有百亿级页面。这种场景下邻接矩阵里 99% 以上的位置存的都是无意义的 0。用具体数字说话。假设图有 10 万个顶点平均每个顶点的出度是 10。邻接矩阵要开 10万 × 10万 的数组按每个元素 1 字节算需要约 10GB。而真实的边只有 10万 × 10 100万条。邻接表呢顶点数组占 10万 × sizeof(头节点)边节点占 100万 × sizeof(边节点)算下来一般也就几十MB 到一两百MB差了不止一个数量级。所以结论很简单稀疏图选邻接表稠密图选邻接矩阵。判断标准就是看边数 E 和顶点数 V 的关系。如果 E 接近 V² 的上限邻接矩阵的空间优势还能靠 O(1) 查询弥补如果 E 远小于 V²邻接表就是唯一合理的选择。1.2 邻接表的存储模型顶点数组 边链表怎么组织才清晰邻接表的本质我自己习惯把它理解成“每个人一张朋友名单”。你有 N 个朋友你的桌上就有一张写着你朋友名字的纸条张三也有自己的一张纸条。要把所有人的朋友关系整理出来只需要把 N 张纸条按编号顺序排好这就成了邻接表。落到代码层面这个模型由两部分组成顶点表一个数组数组下标就是顶点编号每个数组元素是一个“头节点”它包含顶点数据和一条链表的头指针。边链表每个顶点的头指针指向一条链表链表中的每个节点代表一条从该顶点出发的边节点里存的是这条边指向的邻居顶点编号。这个模型的内存布局比邻接矩阵“碎”但换来的是只存储真实存在的边。空间复杂度从 O(V²) 降到 O(V E)对稀疏图是革命性的。代价是查询“u 和 v 是否相邻”不能 O(1) 完成得顺着 u 的链表遍历一遍最坏情况是 O(出度)。这个取舍在工程上完全可接受因为大多数图算法的瓶颈本来就不在单次边查询上。还有一个细节容易踩坑网上的代码和教材里边链表的方向到底是谁指向谁编码风格差异很大。主流有两种出边表每个顶点存的是“从它出发能到达哪些节点”适合遍历出边、做DFS/BFS、算最短路径。入边表也叫逆邻接表每个顶点存的是“有哪些节点指向它”适合做拓扑排序中的入度统计、反向图遍历。最高效的工程做法不是二选一而是建图时同时维护出边表和入边表代价是每个边节点要存两处但很多算法比如Kosaraju求强连通分量就需要两个方向都跑。后面代码示例里我会给一个支持这种需求的实现。2. 完整代码拆解从结构体定义到建图每个字段都有讲究2.1 结构体定义的标准写法与扩展思路来看一份完整的、可以直接编译运行的邻接表实现。先看结构体定义部分。#include stdio.h #include stdlib.h #include string.h // 边表节点代表一条从某个顶点出发的边 typedef struct EdgeNode { int adjvex; // 该边指向的顶点编号 int weight; // 边的权值无权图填0或1 struct EdgeNode *next; // 指向下一条边 } EdgeNode; // 顶点表节点每个顶点对应一个链表头 typedef struct VertexNode { int data; // 顶点数据可以是编号、名称或业务ID int inDegree; // 入度用于拓扑排序可选字段 EdgeNode *firstEdge; // 指向第一条边 } VertexNode; // 图结构顶点数组 顶点数 边数 typedef struct { VertexNode *vertices; // 动态数组大小 vertexNum int vertexNum; int edgeNum; int directed; // 1表示有向图0表示无向图 } Graph;这段代码里有几个字段值得细说。先看adjvex和weight。adjvex是必填字段它决定这条边连向谁。weight看场景如果是带权图比如城市间公路里程、网络拓扑里的链路时延这个字段就得存实际权值如果是无权图统一置 1 即可这样在统计路径长度时就不需要额外判断。再看inDegree。这个字段很多人一开始不理解为什么要存在顶点节点里。拓扑排序算法里最直观的做法是“每次找一个入度为0的顶点删掉它的所有出边”删出边就会影响邻居的入度。如果入度要现算每次都得遍历全图复杂度直接飙到 O(V·E)。把入度作为顶点表的字段维护每次删边时同步更新拓扑排序就能做到 O(VE)。这是一个“用空间预计算换取算法效率”的典型例子。还有directed字段。无向图的每条边要在两个方向各插入一次有向图只插入一次。建图函数里根据这个标志决定插入逻辑。有些实现把这个标志放建图函数外面由调用方自己判断也行但放进图结构的好处是图自己“记得”自己的类型后续写打印、遍历、算法函数时直接查就行不用到处传参数。2.2 初始化、建图、打印三条核心函数的完整逻辑初始化函数负责把顶点数组建好把所有链表头置空。这里的核心问题是不能只开辟空间必须逐个初始化。用malloc分配完数组后内存里的内容是随机的里面的firstEdge指针是个野指针直接拿来当空指针判断会出大问题。所以我习惯写一个initGraph把每个顶点的firstEdge置为NULL、inDegree置为 0。// 初始化图vertexNum个顶点顶点数据默认为0~N-1 Graph* initGraph(int vertexNum, int directed) { Graph *g (Graph*)malloc(sizeof(Graph)); if (!g) return NULL; g-vertexNum vertexNum; g-edgeNum 0; g-directed directed; g-vertices (VertexNode*)malloc(sizeof(VertexNode) * vertexNum); if (!g-vertices) { free(g); return NULL; } for (int i 0; i vertexNum; i) { g-vertices[i].data i; g-vertices[i].inDegree 0; g-vertices[i].firstEdge NULL; } return g; }注意这里我让顶点数据默认等于编号。工程场景下顶点数据可能是一个结构体名字、坐标、业务属性那就把int data换成一个结构体字段并另写数据加载函数。学习阶段用编号最直观。加边函数是邻接表的灵魂。它的核心操作是“头插法”——新边节点插到链表头部。为什么不用尾插法最直接的原因是头插法不需要遍历链表找尾节点时间复杂度 O(1)。但头插法的副作用是遍历出来的邻接顺序是逆序的你按 (0,1)、(0,2) 的顺序加边打印时 1 号顶点的链表会先输出 2 再输出 1。这个不影响任何算法正确性但面试时如果要求输出某个顺序就要注意这个细节。// 添加一条边u为起点v为终点w为权值 void addEdge(Graph *g, int u, int v, int w) { // 插入到u的链表头部 EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex v; e-weight w; e-next g-vertices[u].firstEdge; g-vertices[u].firstEdge e; // 无向图需要反向再插一次 if (!g-directed) { EdgeNode *re (EdgeNode*)malloc(sizeof(EdgeNode)); re-adjvex u; re-weight w; re-next g-vertices[v].firstEdge; g-vertices[v].firstEdge re; g-edgeNum; } g-edgeNum; }无向图情况下edgeNum要加两次这地方特别容易写错。有些教材里edgeNum的定义是“边数”无向图一条边算一条那就应该只在有向图分支里加、或者每加两条才加一口。我这种定义按“实际插入的链表项数”来累计写打印或做复杂度分析的时候心里要有个换算关系。建议代码注释里写清楚这个约定不然后续维护会晕。打印图函数纯粹是检验建图是否正确的工具但它的价值很高——每次写完建图代码第一步就是打印整个邻接表逐个顶点检查链表内容是否符合预期。我见过很多人跳过这一步直接去写遍历算法结果遍历结果完全不对回头查建图建错了浪费大量时间。void printGraph(Graph *g) { for (int i 0; i g-vertexNum; i) { printf([%d] (in:%d):, i, g-vertices[i].inDegree); EdgeNode *p g-vertices[i].firstEdge; while (p) { printf( - %d, p-adjvex); if (g-directed p-weight 0) { printf((w:%d), p-weight); } p p-next; } printf( - NULL\n); } }打印时把入度也打出来因为入度字段经常是算法调试的关键线索。实际开发里我会再加一个“按邻接矩阵形式输出”的辅助函数把邻接表临时转换为矩阵打印方便和手工算的结果对照。2.3 完整代码示例一份可直接跑的基准实现把上面的函数组合起来附上一个建图示例和主函数#include stdio.h #include stdlib.h typedef struct EdgeNode { int adjvex; int weight; struct EdgeNode *next; } EdgeNode; typedef struct VertexNode { int data; int inDegree; EdgeNode *firstEdge; } VertexNode; typedef struct { VertexNode *vertices; int vertexNum; int edgeNum; int directed; } Graph; Graph* initGraph(int vertexNum, int directed) { Graph *g (Graph*)malloc(sizeof(Graph)); g-vertexNum vertexNum; g-edgeNum 0; g-directed directed; g-vertices (VertexNode*)malloc(sizeof(VertexNode) * vertexNum); for (int i 0; i vertexNum; i) { g-vertices[i].data i; g-vertices[i].inDegree 0; g-vertices[i].firstEdge NULL; } return g; } void addEdge(Graph *g, int u, int v, int w) { EdgeNode *e (EdgeNode*)malloc(sizeof(EdgeNode)); e-adjvex v; e-weight w; e-next g-vertices[u].firstEdge; g-vertices[u].firstEdge e; if (g-directed) { g-vertices[v].inDegree; } else { EdgeNode *re (EdgeNode*)malloc(sizeof(EdgeNode)); re-adjvex u; re-weight w; re-next g-vertices[v].firstEdge; g-vertices[v].firstEdge re; g-edgeNum; } g-edgeNum; } void printGraph(Graph *g) { for (int i 0; i g-vertexNum; i) { printf([%d] (in:%d):, i, g-vertices[i].inDegree); EdgeNode *p g-vertices[i].firstEdge; while (p) { printf( - %d(w:%d), p-adjvex, p-weight); p p-next; } printf( - NULL\n); } } int main() { // 测试用例5个顶点的有向图边为 (0-1) (0-2) (1-3) (2-3) (3-4) Graph *g initGraph(5, 1); addEdge(g, 0, 1, 2); addEdge(g, 0, 2, 3); addEdge(g, 1, 3, 4); addEdge(g, 2, 3, 1); addEdge(g, 3, 4, 2); printGraph(g); return 0; }这里的有向图建图方式同时维护了inDegree后续做拓扑排序可以直接用不需要重新统计。测试用例里特意选了带环和不带环的混合结构便于调试。编译运行命令不需要特别说明gcc直接编译就能过。3. 遍历算法怎么在邻接表上跑DFS 和 BFS 的正确姿势3.1 深度优先遍历递归写法、迭代写法、访问顺序差异图的深度优先遍历DFS在邻接表上实现核心思想跟树的前序遍历一致从某个顶点出发沿着第一条未访问的边深入直到走不动再回溯。只是图里可能有环所以必须有visited数组防止死循环。递归写法最直观也是面试手写最常见的void dfsRecursive(Graph *g, int v, int *visited) { visited[v] 1; printf(visit %d\n, v); EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; if (!visited[neighbor]) { dfsRecursive(g, neighbor, visited); } p p-next; } } void dfsGraph(Graph *g, int start) { int *visited (int*)calloc(g-vertexNum, sizeof(int)); dfsRecursive(g, start, visited); // 非连通图的处理对未访问顶点继续DFS for (int i 0; i g-vertexNum; i) { if (!visited[i]) { dfsRecursive(g, i, visited); } } free(visited); }注意这个写法里visited数组用calloc初始化而不是malloc后手动填充 0。calloc会自动把内存清零省一行代码也少一个犯错机会。非连通图处理那段很多人漏掉如果图不连通从一个起点出发只能访问一个连通分量必须遍历所有顶点对没访问过的继续深搜。递归 DFS 的问题是当图很深时比如一条链状的图顶点数几十万递归调用栈会爆掉。工程上要么显式增大栈空间要么改成迭代写法。迭代写法用栈模拟递归过程void dfsIterative(Graph *g, int start) { int *visited (int*)calloc(g-vertexNum, sizeof(int)); int *stack (int*)malloc(sizeof(int) * g-vertexNum); int top -1; stack[top] start; while (top 0) { int v stack[top--]; if (visited[v]) continue; visited[v] 1; printf(visit %d\n, v); EdgeNode *p g-vertices[v].firstEdge; // 为了保持与递归一致的访问顺序可以逆序入栈 while (p) { if (!visited[p-adjvex]) { stack[top] p-adjvex; } p p-next; } } free(visited); free(stack); }这里有个常见困惑迭代写法和递归写法访问顺序可能不一致。原因在于栈是 LIFO 的邻接表里链表节点的顺序本身又是逆序两个逆序叠加后某些场景下访问顺序和递归版本不同。如果题目要求一个特定的遍历序列需要额外处理入栈顺序。这一点面试时主动提出来反而能体现你真的理解 DFS 的机制而不是背代码。3.2 广度优先遍历队列在邻接表上的天然适配广度优先遍历BFS用队列实现。它的访问顺序是逐层扩散先访问起点然后访问起点的所有邻居再访问邻居的邻居。邻接表的链表结构让“取出一个顶点的所有邻居”变得非常自然直接遍历链表即可。void bfsGraph(Graph *g, int start) { int *visited (int*)calloc(g-vertexNum, sizeof(int)); int *queue (int*)malloc(sizeof(int) * g-vertexNum); int head 0, tail 0; queue[tail] start; visited[start] 1; while (head tail) { int v queue[head]; printf(visit %d\n, v); EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; if (!visited[neighbor]) { visited[neighbor] 1; queue[tail] neighbor; } p p-next; } } free(visited); free(queue); }BFS 里有一个经典坑入队时就要标记 visited不能出队时再标记。如果出队时才标记那么同一个顶点可能被多个邻居重复入队——因为它还没被标记每个邻居遍历时都觉得自己发现了新大陆。在带环图里这会导致队列无限膨胀甚至死循环。这也顺便解释了一个编程习惯状态标记的时机要放在状态进入容器的那一刻而不是弹出那一刻。队列我用数组模拟而不是用链式队列。原因是面试或竞赛环境里数组队列更快、更不容易出内存泄漏问题而且容量开vertexNum就够用了。有人可能问为什么不直接用循环队列BFS 中每个顶点最多入队一次普通数组队列不存在“再次写入同一位置”的情况用循环队列反而是冗余。3.3 遍历顺序依赖链表的插入方式这个细节你迟早要面对前面建图用的是头插法导致每个顶点的邻接链表里的顺序和输入顺序相反。这个顺序会影响 DFS、BFS 以及后面要讲的最短路径算法的实际执行路径——尽管不影响最终正确性但会影响中间过程的输出序列。举例说明。现在输入三条边0→1、0→2、0→3。因为每次都头插vertices[0].firstEdge会先指向 33 再指向 22 再指向 1。所以从 0 开始 DFS第一个访问到的邻居是 3而不是输入顺序里的 1。如果你希望遍历顺序和输入顺序一致有两个办法改用尾插法每次找链表末尾再插入复杂度 O(出度)建图时间从 O(E) 变成 O(V·E) 最坏情况。可以额外维护一个tail数组指向每个链表的尾部把尾插降到 O(1)。保持头插法但在遍历时对邻居先收集后排序这种办法适合需要输出特定序列的场景。我个人的经验是学习阶段用头插法就行面试时如果题目要求按照某种字典序输出遍历结果最稳妥的做法是在遍历当前顶点的邻居前先把邻居节点值收集到一个数组并排序再依次递归。这样不管邻接表内部顺序是怎样的输出总是可预期的。4. 邻接表和经典图算法怎么衔接不止是存下来那么简单4.1 拓扑排序邻接表的入度字段一到位代码立刻就简单了拓扑排序是 DAG有向无环图上的经典算法用邻接表实现时有两个方向Kahn 算法BFS思想和 DFS 变种。Kahn 算法是最常用的它依赖于入度统计。有了前面结构体里的inDegree字段Kahn 算法写起来几乎一气呵成先把所有入度为 0 的顶点入队然后依次弹出顶点把它所有出边的终点入度减 1如果某个终点的入度变成 0再把它放进队列。循环结束后如果弹出的顶点数不等于总顶点数说明图里有环。void topologicalSort(Graph *g) { int *queue (int*)malloc(sizeof(int) * g-vertexNum); int head 0, tail 0; for (int i 0; i g-vertexNum; i) { if (g-vertices[i].inDegree 0) { queue[tail] i; } } int count 0; while (head tail) { int v queue[head]; printf(%d , v); count; EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; g-vertices[neighbor].inDegree--; if (g-vertices[neighbor].inDegree 0) { queue[tail] neighbor; } p p-next; } } if (count ! g-vertexNum) { printf(\n图中有环拓扑排序不完整\n); } free(queue); }这段代码最大的优点是用入度字段直接做增减操作不用每次去算入度。但注意运行完拓扑排序后所有顶点的inDegree都被改成了 0如果之后还要继续使用图比如跑其他算法需要重新初始化入度。我的习惯是在拓扑排序函数的入口处先记录一份入度备份或者干脆重新调用一个recalcInDegree函数。4.2 Dijkstra 最短路径邻接表 优先队列的标准组合打法Dijkstra 算法是邻接表最受益的算法之一。如果用邻接矩阵实现每轮找“当前距离最小的未访问顶点”是 O(V)更新所有邻居是 O(V)总复杂度 O(V²)。用邻接表 优先队列最小堆更新操作只涉及真实存在的边摊还下来复杂度降到 O((VE)logV)。在处理稀疏大图时这个差距是决定性的。关键实现点是优先队列里存的是“顶点编号 当前最短距离”的二元组。每次从堆里弹出距离最小的顶点如果它已经被访问过跳过否则标记访问遍历它的邻接链表试图松弛邻居节点。这里有个经验优先队列里可能会存入同一个顶点的多个不同距离版本因为松弛时发现更短距离就会 push 一次新版本所以弹出时要检查“当前距离是否比 dist 数组里记录的更小”如果不是直接忽略。这个检查我见过很多人漏掉结果算法结果没问题但堆里积压了大量无效项性能退化成灾难。// 简化版不包含完整优先队列实现只展示邻接表上的松弛逻辑 // dist[] 初始为 INF; 用数组模拟的最小堆在完整项目中实现 void dijkstra(Graph *g, int start, int *dist) { // 假设这里有一个最小堆 heap每个元素是 (node, distance) // 初始化 dist[start]0将 (start,0) 入堆 while (!heapEmpty()) { int v heapPopNode(); int d heapPopDist(); if (d dist[v]) continue; // 过期的堆条目 EdgeNode *p g-vertices[v].firstEdge; while (p) { int neighbor p-adjvex; if (dist[v] p-weight dist[neighbor]) { dist[neighbor] dist[v] p-weight; heapPush(neighbor, dist[neighbor]); } p p-next; } } }邻接表在这里的意义是松弛邻居时只需要看当前顶点链表里的节点不会把时间浪费在根本不存在的边上。如果图有 10 万顶点、平均出度 10一次 Dijkstra 的实际比较次数大概在百万级换成邻接矩阵光遍历矩阵就要 10 亿次操作。4.3 并查集和最小生成树邻接表如何配合 Kruskal 与 Prim最小生成树的两种经典算法对图存储有不同的依赖。Kruskal 的核心操作是边排序 并查集判环它根本不需要遍历某个顶点的所有邻居只需要把边抽出来排序。所以很多人用邻接表存完图后还要再构造一个“边数组”交给 Kruskal。这种情况下图的存储格式是邻接表还是边集数组区别不大。Prim 算法就不一样了。常规 Prim 需要反复取“离当前已选顶点集合最近的未选顶点”如果每次都扫描所有顶点复杂度 O(V²)。但在邻接表 优先队列的实现里可以做到类似 Dijkstra 的低复杂度每次把一个顶点加入生成树时遍历它的邻接链表把所有连接未选顶点的边插入堆中。邻接表的稀疏性在这里再次发挥作用。整套链路是这样的建图用邻接表 → 遍历邻接表生成边数组 → Kruskal 排序并查集判环或者邻接表 堆实现 Prim。两种路线你都要会面试官可能会问“为什么 Kruskal 更适合稀疏图”这类问题本质就是在考察你对空间与时间复杂度的理解是否到位。5. 缺陷排查手册邻接表代码最容易出错的 7 个地方5.1 从“段错误”到“逻辑错误”一次实战排查过程记录我自己带人写邻接表时见过最多的报错是段错误。经历过一次印象深刻的排查同学建了一个 6 个顶点的图加完边一打印就段错误。代码逻辑看起来完全没毛病后来用调试器跑发现在addEdge里要写入g-vertices[u].firstEdge但g的顶点数组根本没有正确分配。根源是初始化函数里少了一行分配完vertices数组后没有检查是否分配成功。当顶点数到几十万时malloc失败的概率不是零一旦返回NULL连着的第一次加边就会写空指针。所以所有malloc之后第一件事就是判空这是 C 语言编程的底线习惯。给的代码里初始化函数已经加了判空处理实际项目里还要在addEdge里加一个if (!g) return;之类的防御式判断。第二个典型错误更隐蔽无向图建图时只插了一次边。比如addEdge(g,1,3,5)执行后只有vertices[1]的链表里有 3vertices[3]的链表里找不到 1。这个问题最坑的地方在于单看打印结果好像图还不错只是少了半边真正跑 BFS 或连通分量判断时才完全错乱。排查方法很简单打印图时检查对称性——无向图中如果 i 的链表里有 jj 的链表里必须有 i。第三个错误是重复边导致的计数混乱。同一个测试用例里如果不小心把同一条边加了两次比如从文件读数据时没判重邻接表会多出一个平行边节点。这对大多数算法没影响但会让 Kruskal 的边数量统计出错也让最小生成树的正确性无法保证。解决办法有两个建图时判重遍历当前顶点的链表检查有没有已存在同样邻居或者使用哈希表辅助。竞赛和考试场景里一般默认输入没有重复边但工程代码里一定要处理。5.2 常见问题速查表按症状定位到根因我把平时排查邻接表问题时用到的对照表整理出来每个症状都对应最可能的根因和解决手段症状可能原因解决思路打印时崩溃/段错误顶点数组未初始化、malloc失败未判空检查 initGraph 是否循环初始化 firstEdgemalloc 后判空无向图少了半边边无向分支没写反向插入检查 addEdge 中 directed0 分支遍历结果顺序奇怪头插法导致邻接逆序无需修复理解即可如要求顺序改用尾插或排序BFS 死循环visited 标记位置错误入队时标记visited而不是出队时拓扑排序结果为空/不全inDegree 未初始化或建图时忘更新initGraph 中置0addEdge有向分支更新入度链表中出现重复边建图时未判重加边前遍历链表查重或输入预处理求最短路径结果明显偏大weight 字段忘记赋值addEdge 参数w未传给边节点free 时报堆损坏边节点或顶点数组被重复释放写 destroyGraph 时逐个节点释放避免二次free这张表不是让你背的而是排查时对照着定位。我自己的经验是邻接表的问题九成来自“建立图的过程有问题”而不是“遍历算法有问题”所以每次写完先打印图确认图的结构完全正确再往上叠算法能省出大量排错时间。5.3 内存释放的完整实现漏掉一个 free 就是一次内存泄漏图这种动态结构在长期运行的进程里反复创建和销毁是家常便饭。C 语言没有垃圾回收写一个正确的destroyGraph和写建图一样重要。核心逻辑是先遍历所有顶点的链表逐个free边节点最后free顶点数组和Graph结构体本身。void destroyGraph(Graph *g) { if (!g) return; for (int i 0; i g-vertexNum; i) { EdgeNode *p g-vertices[i].firstEdge; while (p) { EdgeNode *tmp p-next; free(p); p tmp; } } free(g-vertices); free(g); }代码简单但有几个细节要强调。第一保存tmp p-next必须在free(p)之前不然就丢了链表后续节点。第二无向图里每条边被存了两份这两个边节点都要释放上面的循环天然会处理。第三如果建图过程中曾经申请过别的辅助结构比如顶点哈希表、边数组也都要在销毁函数里一起处理。另外提醒一下在异常流程里用goto或集中清理函数是 C 工程的老传统如果初始化过程中途失败前面已经分配的资源不能丢写在统一出口处释放。初学阶段可能觉得多余但在资源受限的嵌入式场景或者长期服务的进程里内存泄漏一次两次还能容忍泄漏上千次就是事故了。6. 邻接表的工程化升级与面试实战指南6.1 超越教材的升级方向动态扩容、顶点哈希映射、多态数据承载教材里的邻接表基本固定为“整数顶点编号 int 数据”但在真实项目里顶点往往不是连续的整数而是字符串ID、对象ID、甚至是浮点数坐标。这时候要用哈希映射把外部顶点ID映射成数组下标 0~N-1邻接表内部继续用整数编号操作外部对象映射表单独维护。另一个常见的工程化需求是动态扩容。上文initGraph要求一开始就知道顶点数。有些场景下顶点数是动态增长的比如流式读入数据此时可以按 2 倍或 1.5 倍扩容顶点数组扩容后所有已有顶点的firstEdge指针都要迁移到新数组。这段逻辑比较繁琐建议封装成ensureCapacity函数而且扩容后要重新分配新数组、逐个复制旧顶点、释放旧数组避免指针悬挂。还有多态数据承载的问题。如果每个顶点要存“城市名 人口 坐标”这类复合信息VertexNode里的int data就要扩展成一个结构体指针或者用void*指向业务数据。C 语言里void*用起来稍显繁琐但换来的是通用性。C 或 Rust 里可以用模板或泛型设计思路一致图结构只负责拓扑关系顶点内容由业务层填充。6.2 面试题目最爱的追问方向和应对模板面试手写邻接表时除了基础代码面试官几乎一定会追问几个方向。我把常见的整理出来“为什么不用邻接矩阵”答稀疏图下空间复杂度从 O(V²) 降到 O(VE)。进一步要能说出“当 E 接近 V² 时邻接矩阵的 O(1) 边查询才值得”这种权衡分析。“遍历过程中怎么避免重复访问”答必须用 visited 数组。追问“为什么树遍历不需要 visited”因为树没有环图可能有环。“如果图特别大内存放不下怎么办”答考虑外部存储 分块加载或者用数据库图存储方案。邻接表本身解决不了超大规模问题需要分布式图计算框架。这一题更多考的是系统设计思维。“如果是从文件里读一个很大的图你会怎么建邻接表”答先读第一行拿顶点数和边数预分配顶点数组然后逐行读边数据每条边addEdge。如果边数特别多还要考虑用缓冲读取而不是scanf逐个读。“你的 addEdge 能处理自环和平行边吗”答自环可以的插入逻辑不排斥 uv平行边也可以插入但某些算法需要额外去重。主动讲出这个问题比被问到时才支支吾吾好得多。我建议你去面试之前把“邻接表 DFS BFS 拓扑排序”这四个代码块手写三遍。第一遍看书写第二遍默写第三遍在白板上画着讲。等你讲的时候能讲清楚“这个inDegree字段为什么而存在”“这个visited为什么入队就要置为1”基础知识基本就稳了。6.3 不同语言实现邻接表的差异C、C、Python、Java 的建模方式如果参加在线笔试或做工程实践语言选择会影响邻接表的具体写法。C 语言最直接用 struct 指针但要自己管内存。C 可以使用vectorint adj[N]或vectorvectorint adj每行就是一条链表插入用push_back省了指针操作。Java 用ArrayListInteger[] adj同样省心。Python 更常见的是直接用字典adj {0: [1,2], 1: [3], 2: [3]}。这其实就是邻接表的动态版。有向图、无向图的区别在于是否双向 append。Python 写图算法调试效率极高但性能和内存控制不如 C。算法竞赛里 C 的邻接表有人喜欢用vectorpairint,int adj[N]存带权图简洁高效强烈推荐。语言可以换但核心思想是通用的顶点数组/容器 每个顶点关联一个邻居列表。把 C 版本的逻辑吃透了换成任何语言都只是语法层面的翻译。这也是为什么我一直建议先学 C 版本邻接表因为它把存储结构、指针操作这些底层细节全部暴露出来让你真正理解“一个顶点怎么找到它的所有邻居”。7. 从一份代码到一套方法论邻接表还能怎么扩展7.1 邻接表到邻接多重表与十字链表了解兄弟方案去理解取舍邻接表不是图存储的唯一结构学习框架里通常还会提到邻接多重表和十字链表。邻接多重表专门处理无向图每条边用一个节点表示同时挂在两个顶点的链表上解决“无向图每条边存两份”的内存浪费和同步更新问题。十字链表则是有向图的进阶方案同时维护出边和入边每条边节点同时处于两个链表中一个从弧尾出发的出边链一个指向弧头的入边链。这些进阶结构原理上不复杂但代码实现比邻接表繁琐得多。我个人建议初学阶段把邻接表吃透就够应付绝大多数考试和面试。碰到“为什么这里用十字链表”这类问题核心逻辑是如果你要频繁遍历反向边比如求强连通分量十字链表能让你同时拥有出边和入边而不需要额外维护两个邻接表。理解到这一层就够了真的让你手写十字链表的机会并不多。7.2 邻接表在后端系统里的真实案例推荐系统、知识图谱、链路追踪邻接表不只是考试题。我做过一个轻量的用户关系分析服务用户数大概几百万每个用户平均关注几十个人用 PostgreSQL 存关系表是可以的但每次做两层关系扩展要频繁 JOIN性能不理想。后来在内存里直接用邻接表Go 语言里用map[int][]int缓存用户关系配合 BFS 做共同关注推荐单机扛住了每秒几百次的查询。另一个典型的邻接表应用是知识图谱的图查询引擎。知识图谱本质是海量带标签的有向图每条三元组就是一条带权边。为了支持“从某个实体出发找它的邻居实体”这种查询底层的索引结构也是邻接表的变体每个实体维护一个关系列表列表项是“关系类型 目标实体”。这类系统叫属性图存储但底层思想仍然是“顶点 邻居列表”。链路追踪系统也大量使用树/图结构表达调用链。一次请求会经过多个服务形成一棵调用树多个请求叠加后就变成一张复杂的调用图。监控面板上画出的图表底层存储往往就是一张邻接表每个服务是顶点每次 RPC 是边需要时从某个入口顶点开始 DFS 或 BFS 展开调用链。这些场景共同说明一件事邻接表不是停留在课本上的玩具凡是遇到“点与点之间有连接关系、且连接数量远小于点对总数”的数据邻接表就是最自然的第一选择。学会在数据结构层面抽象问题比学会某一种语言问法更有长期价值。7.3 从邻接表到图计算框架什么时候你需要抬头看更大的世界邻接表再高效也有限度。当图的规模超过单机内存时比如几十亿顶点、几千亿边的社交关系图你就不能再用“一个数组 一堆链表”的本地模型而要考虑分布式图计算框架。这些框架内部也会用邻接表思想——每个分区存储一批顶点及其出边——但跨机器的通信、数据分区策略、容错机制已经远远超出普通数据结构课程的范畴。学习路径上我建议你在掌握了邻接表之后再看两个方向一是图数据库比如以原生图存储为卖点的产品它的查询本质是“从顶点走邻居”理解邻接表能帮你快速理解索引结构的设计动机二是图算法平台比如批处理或流式的图计算引擎里面 Pregel 模型的“每个顶点接收消息、发送消息”机制也和 BFS 的逐层扩散有精神上的相通。从这个意义上说邻接表是你进入图计算世界的第一个正式入口。它很简单但一点都不肤浅——后续学习诺大图算法至少有一半时间你在做的事情仍然是“放在邻接表上的迭代”。我自己用过邻接表这么多年最深的体会是**图这种结构难点从来不是代码而是建模——你能不能一眼看出一个问题可以用图来表达然后选对一个合适的存储方式让后续算法跑得又快又稳。**邻接表就是这个选型金字塔的底座。把它彻底吃透你会发现在最短路径、拓扑排序、连通分量这些常见问题上你开始有能力自己设计和调试了而不是每一步都得去查别人的模板代码。如果你现在正对着书里的邻接表代码发懵我的建议很简单别只看动手抄一遍抄完加几条边打印出来再删掉打印函数换成 BFS 试试。三遍下来这个数据结构的每一根指针、每一个字段就都长在你脑子里了。