图存储详解：邻接矩阵与邻接表转换及易错点

简介这份资源面向正在学习数据结构、需要攻克图存储难点的学生与编程初学者聚焦图的邻接矩阵与邻接表两种存储结构及其相互转换。内容围绕有向图展开包含邻接矩阵的二维数组表示、邻接表的顶点与边节点结构定义以及MatToList、ListToMat、DispMat、DispAdj等核心函数的实现思路并延伸到手动输入图信息后完成存储方式转换的完整程序设计涉及动态内存分配与释放等易错细节。资源包共1个docx文件约55KB以实验报告形式组织目的、问题描述、要求与完整C语言源码便于对照阅读与上机复现。目前已有8614人学习适合作为课程实验参考或考前梳理图存储知识的练习材料帮助读者理解稠密图与稀疏图下两种存储方式的取舍并为后续网络路由、图算法等应用打下基础。1. 图的两种存储一张知识地图先摆出来图的存储这块很多人第一反应是「邻接矩阵和邻接表嘛背过」真到写代码或者做题时却卡在转换和边界上。其实整个方向就一张地图顶点集怎么存、边集怎么存、两者怎么互转、转换时哪些信息会丢。邻接矩阵用二维数组arcs[i][j]表达「i 到 j 有没有边、权值多少」查询 O(1)空间 O(n²)邻接表给每个顶点挂一条边链表只存实际存在的边空间 O(ne)遍历某点邻居 O(degree)。有向图矩阵不对称、无向图对称这是判断写没写反的第一道关。适合正在学数据结构、准备实验或考试复习的人把这张地图先立住后面每个模块都是往格子里填细节。2. 邻接矩阵二维数组里的图长什么样2.1 结构定义与三个核心字段邻接矩阵的本质是一个n×n的二维数组行下标是起点列下标是终点。教材和实验里常见的定义长这样#define MAX_VERTEX_NUM 20 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点表存顶点本身的信息 AdjMatrix arcs; // 邻接矩阵存边/权值 int vexnum, arcnum; // 顶点数、弧数 } MGraph;三个字段各管一件事vexs负责「顶点是谁」arcs负责「边在哪、多重」vexnum/arcnum负责「规模多大」。复习时最容易忽略的是arcnum——它不参与矩阵存储但转换、校验、输出统计都要用漏维护就会在转换后对不上账。矩阵里0通常表示无边INF如 32767表示不可达正数表示权值这三个语义必须在整份代码里统一否则DispMat打印和转换判断会互相打架。2.2 有向图与无向图的矩阵差异同样是矩阵有向图和无向图的写法差一个对称性维度有向图无向图矩阵对称性一般不对称一定对称一条边写入几个格子只写arcs[i][j]arcs[i][j]和arcs[j][i]都写第 i 行含义从 i 出发的边与 i 相连的边第 i 列含义指向 i 的边与 i 相连的边重复度怎么算出度行非零数入度列非零数度行非零数实验里明确用的是有向图所以MatToList只按行扫描、只建出边链表这是对的。如果换成无向图还照抄这段就会漏掉一半边——这是转换题里最常见的翻车点之一。判断方法很简单转换完把邻接表还原回矩阵和原矩阵逐格比对无向图必须对称不对称就是漏写了反向边。2.3 打印与初始化DispMat的细节DispMat看着只是双重循环打印但它承担了「肉眼校验」的职责写法上有讲究void DispMat(MGraph *g) { int i, j; for (i 0; i g-vexnum; i) { for (j 0; j g-vexnum; j) { if (g-arcs[i][j] INF) printf(%3s, ---); // 不可达用 --- 占位对齐好看 else printf(%3d, g-arcs[i][j]); } printf(\n); } }%3d和%3s的宽度要一致否则矩阵列会错位复习时对不上行列。INF单独判一次是为了把「不可达」和「权值为 0 的边」区分开——如果图里允许 0 权边那0就不能再当「无边」用得换一个哨兵值。这个坑在加权图里非常隐蔽矩阵初始化全填 0结果 0 权边被当成无边转换后边就凭空消失了。稳妥做法是初始化填INF对角线填 0边写入时再覆盖。3. 邻接表链表挂顶点空间花在刀刃上3.1 边结点与顶点结点的两级结构邻接表是「数组 链表」的混合结构分两级typedef struct ArcNode { // 边结点 int adjvex; // 这条边指向哪个顶点下标 struct ArcNode *nextarc; // 同起点的下一条边 int info; // 权值等附加信息 } ArcNode; typedef struct VNode { // 顶点结点 VertexType data; // 顶点信息 ArcNode *firstarc; // 第一条出边 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; // 顶点数组每个元素挂一条链表 int vexnum, arcnum; } ALGraph;vertices[i]是第 i 个顶点的「头」firstarc指向它的第一条出边顺着nextarc走完就是 i 的全部邻居。这里的关键认知是邻接表只存「存在的边」所以空间是 O(ne)稀疏图优势明显代价是查「i 到 j 有没有边」要遍历 i 的链表最坏 O(n)不像矩阵 O(1)。复习时把这两句对照记选择题基本不会错。3.2 头插法建表与遍历顺序MatToList建表用的是头插法代码骨架是for (i 0; i n; i) { for (j n - 1; j 0; j--) { // 倒序扫描配合头插 if (g-arcs[i][j] ! 0) { p (ArcNode *)malloc(sizeof(ArcNode)); p-adjvex j; p-info g-arcs[i][j]; p-nextarc G-vertices[i].firstarc; // 新结点指向原表头 G-vertices[i].firstarc p; // 表头前移 } } }头插法的效果是「后插入的排在前面」所以内层循环从n-1倒着扫最终链表顺序才和矩阵列下标从小到大一致。如果正着扫又用头插输出就是逆序——结果不算错但和教材示例对不上考试默写时容易被判「顺序不符」。这里还有个易忽略点G-vertices[i].firstarc必须先置NULL否则野指针会让链表接到随机内存上程序时好时坏属于典型的玄学 bug。3.3DispAdj输出与空顶点处理DispAdj遍历每个顶点沿链表打印邻居下标for (i 0; i G-vexnum; i) { p G-vertices[i].firstarc; if (p ! NULL) printf(%3d:, i); // 有出边才打印行首 while (p ! NULL) { printf(%3d, p-adjvex); p p-nextarc; } printf(\n); }if (p ! NULL)这一句是出度为零的顶点汇点不打印空行保持输出干净。但要注意如果题目要求「每个顶点都占一行」这个判断就得去掉改成无条件打印行首。两种写法没有对错取决于输出格式要求复习时看清题干再定。另外info字段在纯拓扑输出里用不上但转换回矩阵时必须带上否则权值全丢——这是下一章转换的核心。4. 双向转换矩阵与邻接表怎么互推4.1 矩阵转邻接表按行扫、只建出边MatToList的完整逻辑可以拆成三步清空表头、双重循环扫矩阵、维护规模字段。第一步把G-vertices[i].firstarc全部置NULL防止残留指针第二步按行 i 扫列 jarcs[i][j] ! 0就为 j 建一个边结点挂到 i 的链表上第三步把vexnum和arcnum抄过去。判断条件用! 0还是! INF取决于矩阵初始化约定如果无边填 0就用! 0如果无边填INF就得用! INF ! 0否则会把INF当成一条权值 32767 的边建出来转换结果直接多出一堆假边。4.2 邻接表转矩阵先清零、再按链表填ListToMat是反向操作顺序很关键for (i 0; i n; i) for (j 0; j n; j) g-arcs[i][j] 0; // 第一步矩阵清零 for (i 0; i n; i) { p G-vertices[i].firstarc; while (p ! NULL) { g-arcs[i][p-adjvex] p-info; // 第二步按边填权值 p p-nextarc; } } g-vexnum n; g-arcnum G-arcnum;清零必须在填值之前否则旧矩阵的残留值会混进来。填值用p-info而不是写死 1是为了保住权值如果只关心连通性写 1 也行但那就丢了加权信息。转换完arcnum直接抄邻接表的不再重新数——因为邻接表的arcnum在建表时已经维护过重数一遍反而容易和链表实际结点数对不上。这里有个血泪经验转换函数最好成对写MatToList和ListToMat互为逆操作写完立刻做一次「矩阵→表→矩阵」往返逐格比对能一次性抓出绝大多数下标写反、条件写错的问题。4.3 转换的复杂度与适用场景操作时间复杂度说明矩阵转邻接表O(n²)必须扫完整矩阵稀疏图也躲不掉邻接表转矩阵O(n² e)清零 O(n²)填边 O(e)矩阵查边O(1)直接下标访问邻接表查边O(degree)遍历起点链表矩阵空间O(n²)稠密图划算邻接表空间O(ne)稀疏图划算这张表是复习时的「选型依据」稠密图、频繁查两点连通性选矩阵稀疏图、频繁遍历某点所有邻居如 BFS/DFS选邻接表。转换本身没有「更优」一说只有「当前操作需要哪种视图」。实验要求两个程序分别以矩阵和表为起点互转本质就是让你把两个方向都手写一遍体会各自的遍历方式差异。5. 易错点清单转换题里最容易翻车的五处5.1 易错点一无边哨兵值不统一为什么漏矩阵初始化用 0判断却写! INF或者反过来代码能跑但结果多边少边。怎么补在文件头统一定义#define INF 32767初始化、判断、打印三处引用同一个宏改一处全改。5.2 易错点二头插法配正序扫描导致逆序为什么漏只记住「头插」忘了头插会把顺序翻过来输出和示例对不上还以为是逻辑错。怎么补要么内层倒序扫配头插要么正序扫配尾插二选一写完拿 3 个顶点的小图手推一遍链表顺序。5.3 易错点三表头指针没置空为什么漏malloc出来的ALGraph里firstarc是随机值直接头插会接到野指针上程序时崩时不崩。怎么补建表第一步无条件for (i0;in;i) G-vertices[i].firstarc NULL;养成肌肉记忆。5.4 易错点四无向图只建单向边为什么漏有向图代码直接套到无向图上只写了arcs[i][j]漏了arcs[j][i]转换后矩阵不对称。怎么补转换完做对称性断言无向图逐格检查arcs[i][j] arcs[j][i]不等就补反向边。5.5 易错点五arcnum不维护或重复计数为什么漏只关注链表和矩阵忘了规模字段转换后统计对不上或者转换时又数一遍链表和原值冲突。怎么补arcnum只在建图时数一次转换时直接抄不重算往返转换后比对arcnum是否一致作为自检项。6. 复习落地一张自检表加一个往返测试习惯复习这块内容最有效的方式不是反复看代码而是拿一张自检表逐项过再用「往返转换」当后悔药。下面这张表可以直接抄到笔记里每复习一遍打一次勾检查项通过标准常见失分结构定义矩阵三字段、表两级结点齐全漏arcnum、漏info哨兵值初始化/判断/打印同一宏0 与 INF 混用建表顺序头插配倒序或尾插配正序输出逆序表头初始化建表前全部置 NULL野指针随机崩有向/无向无向图双向写、转换后对称只写单向规模字段转换时抄不重算arcnum对不上往返一致矩阵→表→矩阵逐格相等权值丢失、多假边具体怎么练先手写一个 4 顶点、5 条边的小有向图矩阵和邻接表各画一遍然后照着代码把MatToList和ListToMat各默写一次重点默写循环边界和判断条件最后跑一次往返把原矩阵和还原矩阵并排打印逐格比对。往返测试的价值在于它是「黑匣子」——你不需要逐行调试只要两端相等中间大概率没错不相等就顺着链表和矩阵的差异定位到具体顶点。手动输入那部分也别跳过。实验要求把程序完善成手动输入任意图这一步练的是「输入校验」顶点数、边数、每条边的起点终点权值输错一个下标就越界。加一句if (u 0 || u n) continue;之类的边界判断比事后调试省事得多。从那以后我每次写图相关的转换都强制走一遍「小图手推 → 默写核心循环 → 往返比对」三步宁可多花十分钟也不让野指针和哨兵值在考场上给我惊喜。希望这份梳理帮到你。本文还有配套的精品资源点击获取