简介：这份文档面向正在学习数据结构、需要攻克图存储难点的学生与编程初学者，聚焦图的邻接矩阵与邻接表两种存储结构及其相互转换。内容围绕有向图展开，先讲清邻接矩阵的对称性与空间开销、邻接表的链表组织与稀疏图优势，再给出邻接矩阵转邻接表、邻接表转邻接矩阵的完整C语言实现，并支持手动输入任意图信息进行转换，涉及动态内存分配、头插法建表与内存释放等关键细节。资源包共1个docx文件，约55KB，以实验目的、问题描述、程序要求与源码清单的形式组织，便于对照阅读和上机复现。目前已有8613人学习，适合作为课程实验参考或考前梳理图存储转换思路的实操材料。
1. 邻接矩阵与邻接表：同一张图，两种“世界观”
同一张有向图，用邻接矩阵存和用邻接表存，跑出来的遍历结果一模一样，可一旦图变稀疏，两者的内存占用能差出一个数量级。这不是玄学，而是两种存储结构对“图是什么”给出了不同回答：矩阵把图看成一张稠密的二维关系表，表里每个格子都要有值，哪怕绝大多数格子是 0；邻接表把图看成一组顶点的出边清单，只记录真实存在的边。搞懂这两种“世界观”的转换，不只是为了应付一道数据结构作业，而是理解后面所有图算法——最短路、拓扑排序、强连通分量——为什么在不同场景下要换存储结构。这份资源用一份完整的 C 语言实现，把矩阵转邻接表、邻接表转矩阵两条路径都摊开给你看，正好是拆解底层机制的好样本。
2. 邻接矩阵：为什么 O(1) 查询要用 O(n²) 空间换
2.1 二维数组本身就是一张“关系全表”
邻接矩阵的底层就是一个int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]的二维数组。它的设计动机非常直接：图的本质是顶点对之间的关系，那就用行下标表示起点、列下标表示终点，arcs[i][j]的值表示这条边的权重。查询“i 到 j 有没有边”只需要一次数组下标寻址，时间复杂度 O(1)，这是矩阵存储最大的卖点。
代价藏在空间里。n 个顶点的图，矩阵固定占 n² 个存储单元，跟实际有多少条边完全无关。资源里MAX_VERTEX_NUM定义为 20，意味着哪怕你只存 3 条边，也要先占掉 400 个 int 的位置。这就是典型的“用空间换时间”，而且换得相当奢侈。常见的实现思路是：稠密图（边数接近 n²）用矩阵不亏，稀疏图（边数远小于 n²）用矩阵就是纯浪费。
矩阵还有一个隐含约定值得注意：对角线arcs[i][i]通常为 0，表示顶点到自身没有边；而无边的位置也填 0。这就带来一个歧义——0 到底表示“没有边”还是“权重为 0 的边”？资源里用INF（32767）来标记无穷大，DispMat打印时遇到INF输出---，说明作者意识到了这个区分，但初始化时又统一填 0，这个不一致后面会讲到，是个真实的坑。
2.2 结构体把顶点表、矩阵、计数打包在一起
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef int VertexType; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点表，存顶点自身信息 AdjMatrix arcs; // 邻接矩阵，存边关系 int vexnum, arcnum; // 顶点数、弧数 } MGraph;这段定义里，vexs和arcs是分离的：顶点信息（比如顶点编号或名字）放在一维数组，边关系放在二维数组。这种分离设计的好处是顶点数据和边数据解耦，换顶点类型不影响矩阵布局。vexnum和arcnum冗余存储了规模信息，避免每次遍历都重新数一遍。arcnum在有向图里数的是弧（有向边）的条数，这个值在转换时必须原样传递，否则转换后的图规模信息就错了。
DispMat的打印逻辑也值得看一眼：双重循环遍历 n×n，遇到INF打---，否则打数值。这里用%3d和%3s对齐，是为了让矩阵在终端里排成整齐的方阵。别小看这个对齐，调试图算法时矩阵错位一格，你排查半天可能都发现不了是打印格式的问题。
3. 邻接表：链表头插法如何把稀疏图压回线性空间
3.1 顶点数组 + 边链表的两级结构
邻接表的核心思想是“按起点分组”：每个顶点挂一条链表，链表里每个节点代表一条从该顶点出发的边。空间复杂度降到 O(n + e)，e 是实际边数，稀疏图下优势明显。
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;VNode是顶点数组的元素，firstarc是链表头指针；ArcNode是链表节点，adjvex存终点下标，info存权值。这种“数组套链表”的结构，本质上是把矩阵的每一行压缩成一个只含非零元素的链表。矩阵第 i 行有多少个非零元，邻接表第 i 个顶点的链表就有多长。
3.2 头插法：为什么倒着遍历矩阵
MatToList是矩阵转邻接表的核心，里面有个细节很容易被忽略——内层循环是for(j=n-1; j>=0; j--)，从大到小遍历列。
void MatToList(MGraph *g, ALGraph *G) { int i, j, n = g->vexnum; ArcNode *p; for (i = 0; i < n; i++) G->vertices[i].firstarc = NULL; // 先清空所有链表头 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; } } } G->vexnum = n; G->arcnum = g->arcnum; }头插法的效果是“后插入的排在前面”。如果正序遍历 j 再头插，链表顺序会变成终点下标从大到小；倒序遍历再头插，链表顺序就恢复成从小到大，和矩阵列下标的自然顺序一致。这个技巧在需要保持邻接点有序的算法里很实用，比如某些要求按编号顺序访问邻接点的遍历。代价是每次插入都要改两个指针，但都是 O(1) 操作，整体转换复杂度 O(n²)，因为无论如何都要扫完整个矩阵。
这里有个内存管理的隐患：G是外部malloc出来的，但MatToList内部又给每个ArcNode单独malloc。如果同一个ALGraph被反复转换，旧链表节点不释放就会泄漏。资源里的main只转换一次，所以没暴露问题，但这是真实项目里必须处理的。
4. 反向转换：邻接表回矩阵时，0 和 INF 的边界在哪
4.1 先清零再填边
ListToMat做的是反向操作：先把矩阵全部置 0，再遍历每个顶点的链表，把边填回对应位置。
void ListToMat(ALGraph *G, MGraph *g) { int i, j, n = G->vexnum; ArcNode *p; for (i = 0; i < n; i++) for (j = 0; j < n; j++) g->arcs[i][j] = 0; // 全部初始化为 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; }逻辑很直白：链表里有的边，矩阵对应位置就有值；链表里没有的，保持 0。转换复杂度 O(n² + e)，其中 n² 来自清零，e 来自遍历所有边。如果图很稀疏，清零反而成了主要开销，这也是矩阵存储的固有成本。
4.2 0 值边的歧义：一个设计上的真实裂缝
前面提过，矩阵用 0 表示“无边”，但MatToList的判断条件是g->arcs[i][j] != 0。这意味着如果某条边的权值恰好是 0，它会被当成“没有边”而丢掉。反过来，ListToMat清零后只填链表里有的边，如果原图真有一条权值为 0 的边，转换回来时它还在链表里，能正确填回 0——但下一次再转回邻接表时，它又会被!= 0过滤掉。
这是一个典型的“哨兵值冲突”：0 同时承担了“无边”和“合法权值”两个语义。资源里定义了INF却没用它做初始化，说明作者可能意识到了但没统一。常见的修法是：矩阵初始化用INF表示无边，判断条件改成!= INF，这样 0 权边就能正常保留。这个改动很小，但能消除一整类隐蔽 bug。
提示：如果你的图允许 0 权边或负权边，务必把“无边”的哨兵值和合法权值分开，否则转换过程会静默丢边，而且很难通过打印结果发现。
5. 避坑与排查：转换代码里那些不报错但结果错的坑
5.1 链表头没清空，旧数据串进新图
现象：连续两次调用MatToList转换到同一个ALGraph，第二次的结果里混进了第一次的边。原因：G->vertices[i].firstarc没有在每次转换前重置为NULL，头插法直接把新节点插到了旧链表前面，旧节点还挂在后面。解决：转换函数开头必须有一个独立的循环把所有firstarc置空，资源里MatToList做了这一步，但ListToMat没有对应的“清链表”逻辑，因为它操作的是矩阵，不需要。
5.2 矩阵初始化用 0 还是 INF，决定边会不会丢
现象：带 0 权边的图转换后少了几条边，打印邻接表时某些顶点后面是空的。原因：arcs[i][j] != 0把 0 权边当成了无边。解决：统一用INF初始化矩阵，判断条件改为!= INF，DispMat里对INF打---的逻辑保持不变。这个改动要同时改初始化和判断两处，只改一处会更乱。
5.3 顶点数和弧数没同步，后续算法规模算错
现象：转换后的图遍历时越界，或者弧数统计对不上。原因：MatToList和ListToMat都手动赋值了vexnum和arcnum，如果某条路径漏了赋值，结构体里就是垃圾值。解决：转换函数末尾固定写两行赋值，并且优先从源结构体拷贝arcnum，不要重新数——重新数容易在 0 权边或重复边的情况下数错。
5.4 动态分配的边节点没有释放路径
现象：程序跑久了内存持续上涨，或者用内存检测工具报泄漏。原因：每个ArcNode都是malloc出来的，但没有任何函数负责free。解决：写一个DestroyAdj(ALGraph *G)，遍历每个顶点的链表逐个free，在转换前或程序结束前调用。资源里的main只跑一次所以没暴露，但这是真实代码必须补的一环。
5.5 手动输入时没做边界检查
现象：用户输入的顶点数超过MAX_VERTEX_NUM，或者边下标越界，程序直接崩溃或写坏内存。原因：scanf读进来的值直接当数组下标用，没有校验。解决：读入vexnum后立刻判断是否在1..MAX_VERTEX_NUM范围内，读入每条边的两个端点后判断是否在0..vexnum-1范围内，不合法就提示重输。这类检查在实验代码里常被省略，但一旦要“手动输入任意图形”，它就是稳定性的底线。
6. 设计取舍：什么时候该用矩阵，什么时候该换链表
两种存储结构的取舍，本质上是在“查询模式”和“空间预算”之间做选择。矩阵的 O(1) 边查询适合频繁判断两点是否相邻的算法，比如 Floyd 最短路，它的三重循环天然就是矩阵运算，换成邻接表反而要额外维护距离矩阵。邻接表的 O(degree) 邻接点遍历适合需要枚举某个顶点所有出边的算法，比如拓扑排序、Dijkstra 的松弛操作，稀疏图下能省掉大量对 0 元素的无效扫描。
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²)，与边数无关 | O(n + e)，只存实际边 |
| 查边 i→j | O(1) | O(degree(i)) |
| 枚举 i 的出边 | O(n)，要扫整行 | O(degree(i)) |
| 适合场景 | 稠密图、频繁查边 | 稀疏图、频繁枚举邻接点 |
转换代码本身的价值，不在于“能转”，而在于让你看清两种结构的信息等价性：矩阵里的非零元集合和邻接表里的边节点集合，是同一组关系的两种编码。理解了这一点，你就能在写算法时自由切换表示，而不是被某一种结构绑死。
我自己的习惯是：拿到一个图问题，先估边数。如果 e 接近 n² 的十分之一以上，直接用矩阵，省得链表指针跳来跳去还容易踩空；如果 e 明显稀疏，先建邻接表，需要查边时再临时转矩阵或者用哈希辅助。这个判断我踩过几次坑之后才形成——早期不管什么图都用矩阵，结果一个几千顶点的稀疏图直接把内存吃满，程序还没开始算就挂了。从那以后我每次选存储结构前都强制先算一遍 n² 和 n+e 的量级，再决定用哪个。希望这份拆解帮到你，资源里的完整代码和手动输入版本，值得下载下来对着改一遍，尤其是把 0/INF 那个坑亲手修一次，印象会比看十遍文章都深。
本文还有配套的精品资源，点击获取
