简介这份资源面向正在学习数据结构中图结构的高校学生与编程初学者聚焦图的两种核心存储方式——邻接矩阵与邻接表帮助读者理解二者的结构差异、适用场景及相互转换方法。资源包内含1个docx文档压缩包约55KB文档以C语言代码为主线完整呈现了邻接矩阵与邻接表的类型定义、转换函数与打印函数并配有实验目的、问题描述与具体要求便于对照学习。内容涵盖有向图邻接矩阵转邻接表、邻接表转邻接矩阵的双向实现以及手动输入图信息后完成存储方式转换的扩展任务涉及动态内存分配、链表头插法、矩阵遍历等关键操作同时提醒读者关注内存释放与输入校验等工程细节。目前已有8611人学习下载适合希望夯实图存储基础、提升C语言编程能力的读者参考实践。1. 图的两种存储方式为什么邻接矩阵和邻接表总被放在一起讲如果你正在学数据结构翻到「图」这一章大概率会卡在同一个地方图的存储结构到底选哪个。教材上通常先讲邻接矩阵再讲邻接表然后给一堆定义和伪代码看完还是不知道实际写代码时该用哪个。我当初学的时候也是这样考试能默写一到上机建图就懵。这个问题的本质是图这种数据结构不像数组或链表那样有天然的物理顺序顶点之间的关系是多对多的所以必须额外设计一种映射方式把「谁连着谁」存下来。邻接矩阵用二维数组存邻接表用数组加链表存两种方式各有各的适用场景。选错了不会报错但会在稀疏图上浪费大量内存或者在需要快速判断两点是否相邻时反复遍历链表。这篇文章面向正在学数据结构、准备考研408、或者需要在实际项目里建图跑算法的同学。我会把邻接矩阵和邻接表的底层逻辑拆开给出可以直接编译运行的 C 语言实现再对比它们在时间空间上的真实差异最后说清楚什么场景该用哪个。读完你应该能自己写出建图、遍历、销毁的完整代码而不是只会背概念。2. 邻接矩阵用二维数组把图的边关系压进内存2.1 邻接矩阵的存储逻辑与适用边界邻接矩阵的核心思想非常直接用一个n × n的二维数组matrix[i][j]表示顶点i到顶点j之间是否有边。对于无权图matrix[i][j]取 0 或 1对于带权图matrix[i][j]存权值用一个特殊值比如INF表示不连通。无向图的邻接矩阵沿主对角线对称有向图则不一定对称。这种存储方式的优势在于判断两个顶点之间是否有边的时间复杂度是 O(1)直接查数组就行。增加或删除一条边也是 O(1)。对于稠密图边数接近n²邻接矩阵的空间利用率很高不会有太多浪费。但问题也很明显空间复杂度固定为 O(n²)跟实际边数无关。如果一个图有 10000 个顶点但只有 50000 条边典型的稀疏图邻接矩阵要开 1 亿个元素的数组而实际有用的不到 0.5%。这就是为什么稀疏图要用邻接表。还有一个容易忽略的点邻接矩阵在需要枚举某个顶点的所有邻居时必须扫描整行时间复杂度是 O(n)而邻接表只需要 O(degree) 的时间。如果你的算法频繁做「找出所有与顶点 v 相邻的点」这个操作邻接矩阵会拖慢整体效率。提示考研408中邻接矩阵的存储结构定义通常写作typedef struct { VertexType vexs[MAXV]; EdgeType edges[MAXV][MAXV]; int vexnum, arcnum; } MGraph;这个定义要能默写。2.2 用 C 语言构建邻接矩阵完整代码与参数说明下面是一份可以直接编译运行的邻接矩阵建图代码包含初始化、插入边、打印矩阵和 BFS 遍历。我一般用这份代码做教学演示因为它把每个步骤都拆开了方便对照理解。#include stdio.h #include stdlib.h #include string.h #define MAXV 100 // 最大顶点数 #define INF 65535 // 表示无穷大不连通 typedef struct { char vexs[MAXV]; // 顶点表存顶点名称 int edges[MAXV][MAXV]; // 邻接矩阵存边权 int vexnum, arcnum; // 当前顶点数和边数 } MGraph; // 初始化图顶点数 n边数 e void initMGraph(MGraph *G, int n, int e) { G-vexnum n; G-arcnum e; for (int i 0; i n; i) { for (int j 0; j n; j) { G-edges[i][j] (i j) ? 0 : INF; // 自己到自己为0其余为INF } } } // 插入一条无向边权值为 w void insertEdge(MGraph *G, int u, int v, int w) { G-edges[u][v] w; G-edges[v][u] w; // 无向图对称有向图删掉这一行 } // 打印邻接矩阵 void printMatrix(MGraph *G) { printf( ); for (int i 0; i G-vexnum; i) printf(%4c, G-vexs[i]); printf(\n); for (int i 0; i G-vexnum; i) { printf(%4c, G-vexs[i]); for (int j 0; j G-vexnum; j) { if (G-edges[i][j] INF) printf(%4s, INF); else printf(%4d, G-edges[i][j]); } printf(\n); } } int main() { MGraph G; initMGraph(G, 5, 6); // 设置顶点名称 char names[] {A, B, C, D, E}; memcpy(G.vexs, names, 5); // 插入边 insertEdge(G, 0, 1, 3); // A-B 权值3 insertEdge(G, 0, 2, 1); // A-C 权值1 insertEdge(G, 1, 3, 2); // B-D 权值2 insertEdge(G, 2, 3, 4); // C-D 权值4 insertEdge(G, 2, 4, 5); // C-E 权值5 insertEdge(G, 3, 4, 1); // D-E 权值1 printMatrix(G); return 0; }这段代码里几个关键参数需要说清楚。MAXV是编译期确定的顶点上限实际项目中如果顶点数动态变化要么开足够大的数组要么改用动态分配。INF取 65535 是因为int类型下这个值足够大且不会在加法中溢出如果你用long long可以取更大的值。initMGraph里把对角线设为 0、其余设为INF这是带权图的通用做法如果是无权图对角线设 0、其余设 0 表示无边、1 表示有边。insertEdge函数对无向图要对称赋值两次有向图只赋一次。这个细节在考试中经常考写错方向会导致遍历结果完全不对。打印函数里对INF做了特殊处理否则输出一堆 65535 很难看。运行结果会输出一个 5×5 的矩阵你可以直观看到哪些顶点之间有边、权值是多少。这份代码的时间复杂度初始化 O(n²)插入边 O(1)打印 O(n²)。空间复杂度 O(n²)这是邻接矩阵的固有代价。3. 邻接表用链表把每个顶点的邻居串起来3.1 邻接表的节点结构与空间优势邻接表的核心思路是为每个顶点维护一个链表链表里存所有与该顶点直接相连的邻居。具体来说需要一个顶点数组每个数组元素包含顶点信息和指向第一条边的指针每条边用一个边节点表示包含邻接点下标、边权、指向下一条边的指针。这种结构下空间复杂度是 O(n e)n 是顶点数e 是边数。对于稀疏图这比邻接矩阵的 O(n²) 省了不止一个数量级。比如 10000 个顶点、50000 条边的图邻接矩阵要 1 亿个 int约 400MB邻接表只需要 10000 个顶点节点加 100000 个边节点无向图每条边存两次总共约 110000 个节点内存占用不到 2MB。邻接表的另一个优势是枚举邻居非常快。遍历顶点 v 的邻接链表就能拿到所有邻居时间正比于 v 的度。这在 BFS、DFS、拓扑排序、Dijkstra 等算法中非常关键。但邻接表也有代价判断两个顶点 u 和 v 之间是否有边需要遍历 u 的邻接链表最坏情况 O(n)。而邻接矩阵是 O(1)。另外邻接表的指针操作比数组访问更容易出错内存管理也更复杂特别是在需要动态增删边的时候。注意邻接表表示法不唯一。同一个图如果插入边的顺序不同得到的邻接表链表顺序也不同。考试中如果要求画出邻接表通常按顶点编号从小到大或输入顺序排列题目会说明。3.2 邻接表的 C 语言实现头插法与尾插法的选择下面这份代码实现了邻接表的建图、打印和 DFS 遍历。我用了头插法因为头插法代码更简洁插入时间是 O(1)。尾插法需要额外维护尾指针但链表顺序和输入顺序一致调试时更直观。#include stdio.h #include stdlib.h #include string.h #define MAXV 100 // 边节点 typedef struct EdgeNode { int adjvex; // 邻接点在顶点数组中的下标 int weight; // 边权 struct EdgeNode *next; // 指向下一条边 } EdgeNode; // 顶点节点 typedef struct VertexNode { char data; // 顶点名称 EdgeNode *firstEdge; // 指向第一条边 } VertexNode; // 邻接表图结构 typedef struct { VertexNode adjList[MAXV]; int vexnum, arcnum; } ALGraph; // 初始化 void initALGraph(ALGraph *G, int n, int e) { G-vexnum n; G-arcnum e; for (int i 0; i n; i) { G-adjList[i].firstEdge NULL; } } // 头插法插入无向边 void insertEdgeAL(ALGraph *G, int u, int v, int w) { // 插入 u - v EdgeNode *node1 (EdgeNode *)malloc(sizeof(EdgeNode)); node1-adjvex v; node1-weight w; node1-next G-adjList[u].firstEdge; G-adjList[u].firstEdge node1; // 插入 v - u无向图 EdgeNode *node2 (EdgeNode *)malloc(sizeof(EdgeNode)); node2-adjvex u; node2-weight w; node2-next G-adjList[v].firstEdge; G-adjList[v].firstEdge node2; } // 打印邻接表 void printALGraph(ALGraph *G) { for (int i 0; i G-vexnum; i) { printf(%c - , G-adjList[i].data); EdgeNode *p G-adjList[i].firstEdge; while (p) { printf(%c(%d) , G-adjList[p-adjvex].data, p-weight); p p-next; } printf(\n); } } // DFS 遍历 int visited[MAXV]; void DFS(ALGraph *G, int v) { visited[v] 1; printf(%c , G-adjList[v].data); EdgeNode *p G-adjList[v].firstEdge; while (p) { if (!visited[p-adjvex]) { DFS(G, p-adjvex); } p p-next; } } // 释放内存 void destroyALGraph(ALGraph *G) { for (int i 0; i G-vexnum; i) { EdgeNode *p G-adjList[i].firstEdge; while (p) { EdgeNode *tmp p; p p-next; free(tmp); } G-adjList[i].firstEdge NULL; } } int main() { ALGraph G; initALGraph(G, 5, 6); char names[] {A, B, C, D, E}; for (int i 0; i 5; i) G.adjList[i].data names[i]; insertEdgeAL(G, 0, 1, 3); insertEdgeAL(G, 0, 2, 1); insertEdgeAL(G, 1, 3, 2); insertEdgeAL(G, 2, 3, 4); insertEdgeAL(G, 2, 4, 5); insertEdgeAL(G, 3, 4, 1); printf(邻接表:\n); printALGraph(G); printf(\nDFS 遍历: ); memset(visited, 0, sizeof(visited)); DFS(G, 0); printf(\n); destroyALGraph(G); return 0; }头插法的逻辑是新边节点始终插在链表头部所以node-next firstEdge; firstEdge node;。这样插入是 O(1)但链表顺序和插入顺序相反。如果你希望链表顺序和输入顺序一致改用尾插法遍历到链表末尾再插入插入变成 O(degree)但调试时输出更符合直觉。DFS函数用递归实现visited数组是全局的每次遍历前要清零。递归深度等于图的直径极端情况下可能栈溢出实际项目中建议改非递归或手动模拟栈。destroyALGraph负责释放所有边节点的内存这个函数很容易被忽略但在长时间运行的程序里不释放会导致内存泄漏。运行结果会输出每个顶点的邻接链表和 DFS 遍历序列。你可以对比邻接矩阵的输出验证两种存储方式表达的是同一个图。4. 邻接矩阵 vs 邻接表选型对比与转换方法4.1 时间空间复杂度对比与选型决策表选邻接矩阵还是邻接表核心看图的稠密程度和算法需求。我把关键指标整理成一张表方便对照。对比维度邻接矩阵邻接表空间复杂度O(n²)O(n e)判断 u,v 是否相邻O(1)O(degree(u))枚举 v 的所有邻居O(n)O(degree(v))插入一条边O(1)O(1)头插删除一条边O(1)O(degree)适合的图类型稠密图稀疏图实现难度低中内存管理无需手动释放需手动 free选型时我一般按这个逻辑走先估算边数 e 和顶点数 n 的关系。如果 e 接近 n²比如超过 n²/4用邻接矩阵如果 e 远小于 n²比如 e n log n用邻接表。如果算法需要频繁判断两点是否相邻比如 Floyd 算法优先邻接矩阵。如果算法需要频繁枚举邻居比如 BFS、DFS、Dijkstra优先邻接表。还有一个实际因素邻接矩阵的代码更简单不容易出指针错误。如果图规模不大n 1000用邻接矩阵省心。如果 n 上万邻接矩阵的内存开销就不可接受了。4.2 邻接矩阵转邻接表的代码实现实际项目中经常遇到需要把邻接矩阵转成邻接表的场景比如从文件读入的是矩阵格式但后续算法需要邻接表。转换逻辑很直接遍历矩阵的每一行把非零或非 INF的元素作为边插入邻接表。// 将邻接矩阵转换为邻接表 void matrixToAdjList(MGraph *M, ALGraph *G) { initALGraph(G, M-vexnum, M-arcnum); for (int i 0; i M-vexnum; i) { G-adjList[i].data M-vexs[i]; } for (int i 0; i M-vexnum; i) { for (int j 0; j M-vexnum; j) { // 无向图只处理上三角避免重复插入 if (i j M-edges[i][j] ! INF M-edges[i][j] ! 0) { insertEdgeAL(G, i, j, M-edges[i][j]); } } } }这段代码的关键点是i j这个条件。无向图的邻接矩阵是对称的如果遍历整个矩阵每条边会被插入两次导致邻接表里每条边出现两次。加上i j只处理上三角就避免了重复。有向图则不需要这个条件直接遍历整个矩阵。M-edges[i][j] ! INF M-edges[i][j] ! 0这个判断同时排除了不连通和对角线的情况。如果你的图允许权值为 0 的边需要把! 0去掉只保留! INF。反向转换邻接表转邻接矩阵更简单先初始化矩阵全为 INF然后遍历每个顶点的邻接链表把边权填入对应位置。无向图记得对称赋值。提示转换操作的时间复杂度是 O(n²)因为要遍历整个矩阵。如果原始数据就是边列表直接建邻接表更快不需要经过矩阵中转。5. 避坑指南邻接矩阵和邻接表实现中的五个高频翻车点5.1 无向图忘记对称赋值导致遍历丢边现象用邻接矩阵建有向图正常改成无向图后 BFS 遍历少访问了一半顶点。原因insertEdge只写了edges[u][v] w没有写edges[v][u] w。无向图的边是双向的矩阵必须对称。解决在插入函数里对无向图做两次赋值或者单独写一个insertUndirectedEdge函数。邻接表同理无向图要插入两个边节点。5.2 邻接表头插法导致输出顺序与预期不符现象按 A-B、A-C、A-D 的顺序插入边打印邻接表却输出 A-D、A-C、A-B。原因头插法每次把新节点放在链表头部所以顺序反转。这不是 bug是头插法的固有特性。解决如果要求输出顺序和输入一致改用尾插法维护一个尾指针或者在打印前先反转链表。考试中如果题目要求按编号从小到大排列插入时按编号顺序插入即可。5.3 邻接矩阵 INF 值溢出导致最短路计算错误现象用 Floyd 算法求最短路结果出现负数或异常大数。原因INF取 65535两个INF相加变成 131070如果int是 16 位就溢出了。即使 32 位 int 不溢出INF INF仍然大于INF在取最小值时可能被误判为有效路径。解决INF取一个足够大但不会在加法中溢出的值比如0x3f3f3f3f约 10 亿两个相加不超过int上限。或者在加法前判断是否为INF。5.4 邻接表内存泄漏忘记释放边节点现象程序反复建图和销毁图运行一段时间后内存占用持续上升。原因destroyALGraph没有释放边节点或者只释放了顶点数组没释放链表。解决销毁时遍历每个顶点的邻接链表逐个free边节点最后把firstEdge置 NULL。建议把建图和销毁配对使用用valgrind检查内存泄漏。5.5 DFS 递归深度过大导致栈溢出现象图有上万个顶点且呈链状DFS 遍历时程序崩溃。原因递归深度等于图的直径链状图直径接近 n递归栈帧耗尽栈空间。解决改非递归实现用显式栈模拟递归或者增大线程栈大小。实际项目中我一般直接写非递归版本虽然代码长一点但不会因为图结构变化而崩溃。6. 进阶技巧用邻接表跑 Dijkstra 并验证结果学完两种存储方式最终要落到算法上。我拿 Dijkstra 最短路算法做例子因为它对存储结构的选择非常敏感用邻接矩阵实现是 O(n²)用邻接表加优先队列是 O((ne) log n)。稀疏图上差距巨大。下面是在邻接表上跑 Dijkstra 的核心代码用了一个简单数组做优先队列适合教学生产环境用二叉堆。#include limits.h #define BIG (0x3f3f3f3f) // 在邻接表上跑 Dijkstrasrc 为源点dist 输出最短距离 void dijkstra(ALGraph *G, int src, int dist[]) { int n G-vexnum; int visited[MAXV]; for (int i 0; i n; i) { dist[i] BIG; visited[i] 0; } dist[src] 0; for (int iter 0; iter n; iter) { // 找未访问节点中 dist 最小的 int u -1, minDist BIG; for (int i 0; i n; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) break; // 剩余节点不可达 visited[u] 1; // 松弛 u 的所有邻居 EdgeNode *p G-adjList[u].firstEdge; while (p) { int v p-adjvex; if (!visited[v] dist[u] p-weight dist[v]) { dist[v] dist[u] p-weight; } p p-next; } } }这段代码里BIG取0x3f3f3f3f两个BIG相加不会溢出int。外层循环跑 n 次每次找最小 dist 是 O(n)松弛邻居总共 O(e)所以整体是 O(n² e)。如果用优先队列优化找最小值的部分可以降到 O((ne) log n)。验证方法建一个已知最短路的图手动算出结果跟程序输出对比。比如上面 main 函数里的图从 A 出发到各点的最短路应该是 A0、B3、C1、D5、E6。跑一遍看输出是否一致。如果不一致先检查邻接表建图是否正确打印邻接表再检查松弛条件是否写反。我自己的习惯是每次实现完图算法先用一个 5 到 6 个顶点的小图手动验证确认逻辑无误后再上大规模数据。小图上出错容易定位大图上出错只能靠日志和断点效率差很多。另外邻接矩阵和邻接表可以互相验证同一个图用两种结构各跑一遍算法结果一致才说明实现没问题。希望帮到你。本文还有配套的精品资源点击获取