★ FEATURED ARTICLE 简介学习图的存储结构时邻接矩阵与邻接表是绕不开的核心内容。这份资料面向正在学习数据结构或准备图存储实验的学生围绕有向图的邻接矩阵和邻接表相互转换展开配有完整的实验目的、问题描述、程序要求及C语言实现代码。文档共1个docx文件大小仅55KB便于直接查看和打印目前已获得8612人次的学习下载。内容覆盖DispMat、MatToList、DispAdj、ListToMat等核心函数的实现思路涉及邻接矩阵的对称性、邻接表的头插法构建、动态内存分配与释放等关键细节尤其适合需要动手完成图存储转换实验的初学者。通过对照代码与讲解可直观理解两种存储结构的优缺点及适用场景提升结构体、指针链表和二维数组的综合运用能力。1. 图的邻接矩阵和邻接表存储先搞懂为什么要学它图的邻接矩阵和邻接表存储是数据结构课程里绕不开的入门组合也是面试和刷题里最常被问到的基础建模方式。别小看这两个名字很多人背熟了定义一上手写代码就翻车矩阵初始化漏了权重符号、链表头插导致遍历顺序和书里对不上、无向图只插了一条边却检查了半天。这篇笔记要把两种结构的定义、实现、选型边界和踩坑点一次讲清楚适合正在学图的存储、准备考试或刚开始刷图论题的同学。读完你会发现选矩阵还是选表其实取决于你的图有多“稀疏”以及你的算法到底在频繁做哪一类操作。2. 邻接矩阵O(1) 判断两顶点相邻代价是 O(n²) 空间2.1 结构定义与初始化一维存顶点二维存边邻接矩阵的核心思想是用一个 n×n 的二维数组 arc[n][n] 记录所有顶点对之间的关系。arc[i][j] 的值表示从顶点 i 到顶点 j 的边无权图用 0/1 标记是否存在边有权图存边的权重不存在的边用一个足够大的常量表示。这种存储方式让“判断任意两个顶点是否相邻”变得极其直接就是一次数组下标访问没有任何链式查找过程。定义结构体的时候我习惯把顶点数组、矩阵、顶点数和边数绑在一起形成一张完整图的抽象#define MAXV 100 // 最大顶点数按题目需求调整 #define INF 0x3f3f3f3f // 表示不存在的边足够大且不会溢出 typedef struct { char vertex[MAXV]; // 顶点表存顶点名称或编号 int arc[MAXV][MAXV]; // 邻接矩阵arc[i][j] 存边信息 int vexNum, arcNum; // 当前顶点数和边数 } MGraph;这里有第一个关键决策矩阵初值到底填 0 还是填 INF。如果图里允许出现权重为 0 的边那么初值绝对不能填 0否则你无法区分“无边”和“有权为 0 的边”最短路算法会直接算错。我一般统一用 INF 做初值插入边时再覆盖后续所有判断条件都写if (G.arc[i][j] ! INF)语义非常干净。构造函数做两件事顶点表填入内容矩阵所有元素置为 INF。对于无向图插入一条边还要把对称位置一起更新这是新手最容易漏的一步漏了会导致后续遍历结果完全失真。2.2 建图与 DFS/BFS 遍历队列和递归都要顺手建图的 C 代码可以这么写。假设顶点编号已经压缩到 0~n-1我们只处理边的关系读入每条边的两端和权值void createMGraph(MGraph *G, int n, int m) { G-vexNum n; G-arcNum m; for (int i 0; i n; i) { G-vertex[i] A i; // 顶点用字符标记方便调试 for (int j 0; j n; j) { G-arc[i][j] INF; // 先全部初始化为“无边” } } for (int k 0; k m; k) { int u, v, w; scanf(%d%d%d, u, v, w); // 输入一条边的两端和权值 G-arc[u][v] w; G-arc[v][u] w; // 无向图对称赋值两句都在才正确 } }三个参数的含义n 是顶点数决定矩阵维度m 是边数决定循环次数w 是权值可以是任意整数。G-arc[u][v] w和G-arc[v][u] w这两行必须成对出现缺一行就是有向图的语义了。如果你在实现有向图保留第一行删除第二行即可。遍历时DFS 用递归最直观BFS 用数组模拟队列void dfsM(MGraph G, int v, int visited[]) { printf(%c , G.vertex[v]); visited[v] 1; for (int j 0; j G.vexNum; j) { if (G.arc[v][j] ! INF !visited[j]) { dfsM(G, j, visited); } } } void bfsM(MGraph G, int start) { int queue[MAXV], head 0, tail 0; int visited[MAXV] {0}; queue[tail] start; visited[start] 1; while (head tail) { int v queue[head]; printf(%c , G.vertex[v]); for (int j 0; j G.vexNum; j) { if (G.arc[v][j] ! INF !visited[j]) { visited[j] 1; queue[tail] j; } } } }这两段代码的遍历顺序完全由矩阵行中扫描到的第一个相邻顶点决定。BFS 用手写的数组队列而不是标准库队列是因为在笔试环境里你不知道库函数的封装细节自己维护 head 和 tail 最可控也方便在循环结束后检查队列里的元素。这里唯一的硬性要求是visited数组必须在每次遍历前清零我吃过亏连续跑两次 BFS第二次只输出了一个顶点就结束了原因就是上次的 visited 没重置。2.3 矩阵的适用边界稠密图、判邻、求权邻接矩阵的优点有三个后面做选型时都围绕它们展开判断两个顶点是否相邻是 O(1) 级别拿到一条边的权重也是 O(1) 级别实现某些算法比如 Floyd 全源最短路时代码结构天然贴合矩阵三重 for 循环直接对着数组下标写几乎不需要额外转化。缺点也明显——不管你的图只有 10 条边还是 1000 条边只要顶点数超过 500矩阵就要占 500×500×4 字节约 1MB 空间顶点到 1000 就变成 4MB。这在竞赛或嵌入式环境里可能直接让程序超限。所以邻接矩阵最舒服的场合是稠密图也就是边数接近 n(n-1)/2 的图。稀疏图用它纯属浪费空间遍历时还会额外扫描大量 INF 值白耗时间。我在刷题时判断是否用矩阵就一条标准n 小于 200或者边的数量级是 n²直接矩阵否则把目光转向邻接表。3. 邻接表稀疏图的省空间利器但代码量翻倍3.1 顶点表加边表链式结构的定义邻接表把顶点放进一个数组每个顶点挂一条链表链表的每个节点代表一条从该顶点出发的边。这样存储的总空间是 O(n m)和边数成正比而不是和顶点数的平方成正比。n 很大但 m 很小的图邻接表几乎是为它量身定做的。#define MAXV 100 typedef struct ArcNode { int adjVer; // 指向的顶点编号 int weight; // 边的权重 struct ArcNode *next; // 指向下一条边 } ArcNode; typedef struct VNode { char data; // 顶点数据 ArcNode *firstArc; // 第一条边的链表头 } VNode; typedef struct { VNode vertices[MAXV]; // 顶点表 int vexNum, arcNum; } ALGraph;这里每一层的含义要分清楚ArcNode 是边表节点VNode 是顶点表的单元ALGraph 是整张图的封装。顶点表用固定数组边表用链表动态分配两者组合起来既兼顾了随机访问顶点的需求又避免了矩阵那种平方级空间。顶点编号从 0 开始还是从 1 开始会影响后面 malloc 之后 adjVer 的赋值建议全程序统一不要混用。3.2 建表与遍历头插法带来的顺序坑建邻接表的代码插入边时绝大多数教材采用头插法也就是把新边节点插到链表头部。头插法的好处是 O(1) 完成插入坏处是你会得到和输入顺序完全相反的邻接序列DFS/BFS 的遍历结果也跟着反转。void createALGraph(ALGraph *G, int n, int m) { G-vexNum n; G-arcNum m; for (int i 0; i n; i) { G-vertices[i].data A i; G-vertices[i].firstArc NULL; } for (int k 0; k m; k) { int u, v, w; scanf(%d%d%d, u, v, w); ArcNode *p (ArcNode *)malloc(sizeof(ArcNode)); p-adjVer v; p-weight w; p-next G-vertices[u].firstArc; // 头插法新节点指向原来的第一个节点 G-vertices[u].firstArc p; ArcNode *q (ArcNode *)malloc(sizeof(ArcNode)); q-adjVer u; q-weight w; q-next G-vertices[v].firstArc; // 无向图对称插入 G-vertices[v].firstArc q; } }p 和 q 分别代表正向边和反向边因为无向图的每条边在邻接表里要出现两次。如果你把p-next G-vertices[u].firstArc改成p-next NULL那就变成尾插了语法上没错但遍历时输出的邻接顺序会变成输入顺序。这不是对错问题而是算法输出预期的问题——考试时最好在答案里注明自己用的哪种插入方式。DFS 在邻接表上的写法比矩阵版本简洁不少void dfsAL(ALGraph G, int v, int visited[]) { printf(%c , G.vertices[v].data); visited[v] 1; ArcNode *p G.vertices[v].firstArc; while (p ! NULL) { if (!visited[p-adjVer]) { dfsAL(G, p-adjVer, visited); } p p-next; } }因为每个顶点的邻接点都保存在链表中DFS 扫描时只需要沿着 next 走一遍不用像矩阵那样在整行里盲目寻找有值的位置。这个差异在稀疏图里是实打实的性能收益在笔试里体现为“用邻接表建图的程序比矩阵先跑完输入”。如果求一个顶点的度无向图直接统计边表链表长度就行这也是邻接表对“求度”操作友好的原因。3.3 边的方向与入度出度好算入度要动点脑筋邻接表天然擅长表示“从某个顶点出发的边”也就是出度。想算入度得把整张表扫一遍统计有多少边表节点的 adjVer 等于目标顶点。如果题目里反复需要入度比如拓扑排序、Kahn 算法常见的补法是再维护一个 inDegree[] 数组建图时每次插入边顺手累加目标顶点的入度这样查入度就从 O(m) 降到 O(1)。还有一种做法是建“逆邻接表”把邻接表里边的方向反过来存入度变成出度代价是空间翻倍、插入逻辑多写一遍。实际工程里很少单独用逆邻接表通常是为特定算法临时构建。这里提一句是想强调图的存储结构设计始终服务于操作不是背完定义就结束。等你真的动手写拓扑排序的时候会体会到 inDegree 数组比临时扫全表省心得多。4. 两种存储怎么选五个维度定生死4.1 时间与空间一张表看清差异维度邻接矩阵邻接表空间复杂度O(n²)O(nm)判断 u、v 是否相邻O(1)O(degree(u))找某个顶点的所有邻接点O(n)O(degree(v))求某个顶点的出度O(n)O(1)直接数链表长度求某个顶点的入度O(n)O(m) 或维护数组后 O(1)适合的图稠密图稀疏图代表算法FloydDijkstra、BFS/DFS这张表是选型时最常用的依据。判断相邻这一列特别关键如果你写的算法频繁做“两个顶点是否连通”的判断矩阵的 O(1) 优势会压倒所有空间顾虑反过来如果你的算法主要是沿着边扩展BFS、DFS、Dijkstra邻接表能直接把邻接点遍历出来矩阵反而要在一行里反复做无效扫描。4.2 稀疏 vs 稠密临界点在哪工程上的经验公式当边数 m 小于 n²/4 的时候邻接表的空间和时间优势都比较明显。n²/4 是一个很粗糙的估算界限不是为了精确而是为了让你在写代码前快速判断方向。举个例子n1000 的图矩阵要开 1000×1000 的 int 数组约 4MB而邻接表只存 m 个边节点如果 m2000边表加顶点表也就几十 KB 量级差距是数量级的。反过来说一个 50 个顶点的完全图边数 1225矩阵只占 50×50×4 约 10KB代码逻辑也更简单此时硬上邻接表只是给自己增加 malloc 和指针操作的复杂度。另外凡是题目里明确给出了“权重”“快速求两点距离”的口吻多半暗示你用矩阵。4.3 按场景定选型刷题和项目里怎么决策把这一节当做一个决策树来记题目要求多次查两点是否连通选矩阵要求从某个点反复扩展邻接点选邻接表顶点数很小但边很密选矩阵顶点数超 500 且边数明显少选邻接表题目需要多次删除边矩阵的删除是直接置 INF邻接表的删除是遍历链表删节点前者更省事。我自己的习惯是没有明确要求时先读 n 和 m 的数量级n 不超过 200 就无脑矩阵超过 200 就看 mm 接近 n² 用矩阵否则用邻接表。这个决策在多数题目里不会出错也能让你少写一半代码。实际工程项目里图往往来自日志、社交关系、传感器网络基本都是稀疏图所以工业界的默认选择几乎都是邻接表或者配一个稀疏矩阵表示的第三方库。5. 避坑指南图存储实现的 5 个高频翻车点5.1 数组越界下标从 0 开始还是从 1 开始没有第二次机会现象程序在输入边时偶尔崩溃有时却能跑通越界发生在顶点编号等于数组大小的地方属于典型的“玄学崩溃”。 原因题目给的顶点编号从 1 开始而结构体里数组按 0 开始申请编号最大是 n但数组下标只到 n-1。 解决开数组时统一按 MAXV 的上限多开一位例如arc[MAXV1][MAXV1]顶点编号直接当下标用或者所有读入的编号先减一再存。最怕的是两种方式混写建图时用原编号遍历时又按下标访问后患无穷。我的血泪经验是写代码前先在注释里写明“本次实现顶点编号从几开始”再看输入样例决定要不要减一。5.2 无向图只赋值了一边遍历结果悄悄出错现象BFS、DFS 的遍历序列和手推结果不一致某些顶点根本没有被访问到程序却不报错。 原因插入一条无向边时只写了arc[u][v] w漏了arc[v][u] w或者邻接表里只插了 p 节点漏了对称的 q 节点。这种错误隐蔽性高因为图还是能遍历出一部分顶点。 解决写一个insertEdge辅助函数无向图在里面统一做对称插入有向图只插一条。封装成函数后就不存在“这次忘了写另一边”的情况了。数据量大时肉眼查代码很难发现这个遗漏尽早封装是唯一可靠的解法。5.3 INF 和 0 混用有权为 0 的边被判成无边现象带权图里一条权重为 0 的边始终被当作不存在最短路算法结果全错而且很难排查。 原因矩阵初值用了 0 表示无边和真正的 0 权边冲突或者初值用了 INF但判断无边的条件写成了arc[i][j] 0。 解决统一以 INF 为初值所有判边逻辑都写arc[i][j] ! INF。读取边时即使权重为 0 也照常赋值只有初始化阶段用 INF。这一点在做 Dijkstra 相关题目时特别重要0 权边不是边界情况而是经常出现的正常输入。5.4 邻接表遍历顺序和预期不符现象用书里的样例数据建图DFS 输出顺序却和书上的答案不一致于是开始怀疑代码写错了。 原因头插法让后输入的边成为链表头遍历时后边的边先被访问。教材里如果用了尾插法顺序自然不同你拿头插法的输出去对尾插法的答案当然对不上。 解决这不是错误而是存储定义带来的差异。考试时建议先说明自己用的是头插法还是尾插法再写出预期顺序代码里如果希望保持输入顺序就实现尾插每个顶点插入时遍历链表找到尾部。这个翻车点在复试上机里很常见提前确认教材用哪种插入方式能省一小时。5.5 内存泄漏和 visited 状态残留现象邻接表建图过程中 malloc 了不少边节点程序结束后没有释放或者连续两次调用遍历函数第二次的输出结果不对。 原因前者是忽略了无向图每条边要 malloc 两次释放时也得遍历每个顶点的链表逐个 free后者是 visited 数组定义在循环外部上一次遍历结束后没有清零。 解决调试阶段写一个freeGraph把每条边都释放掉visited 数组的初始化放在每次调用 BFS/DFS 的函数内部不要依赖外部状态。内存问题在短小的刷题代码里不致命但如果你在做跨平台的桌面工具或服务端图处理模块泄漏就是实打实的线上事故。6. 进阶动态扩容、编号映射与面试延伸6.1 顶点数不固定时的动态方案固定数组的写法只能在已知上限时使用。如果题目不告诉你最大顶点数顶点表可以用 realloc 动态扩展边表每次 malloc 新节点。核心扩展思路就一段代码int newCap oldCap * 2; VNode *tmp (VNode *)realloc(G-vertices, newCap * sizeof(VNode));realloc 之后要立刻检查返回值是否为 NULL并顺手把新增区域的 firstArc 初始化为 NULL。这段代码平时用不到但一旦遇上顶点规模逐步增长的构造场景能帮你省掉一次重写整张图的时间。6.2 大编号顶点的压缩映射邻接矩阵和邻接表都面临一个实际问题顶点编号可能很大比如 10⁹但实际顶点总数只有几百个。此时直接用编号开数组会爆内存常见的做法是用哈希表把原始编号压缩到 0~n-1 的连续区间再按压缩后的编号建图。邻接表对此尤其友好因为压缩后的 n 只是顶点表数组的长度不再受制于编号数值的上限。面试延伸图论题里能快速写出正确存储结构的候选人往往比只会套模板的更容易过。面试官不会直接问“什么是邻接矩阵”而是给一个具体场景让你分析复杂度并动手写结构。矩阵和邻接表也不是互斥的一道题里混合使用很常见矩阵排序连通性邻接表跑最短路。你只要把复杂度表记牢再亲手把两个版本的建图代码各写三遍考场上基本不会慌。最后说个我的习惯不管用哪种存储写完后我都会用一个三个顶点的三角形图做最小验证——从任意顶点出发BFS 和 DFS 手推一遍结果再对照程序输出。这套验证几分钟就能做完却能挡住绝大多数建图错误。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
