图邻接矩阵创建全解析：C语言结构体定义、初始化与常见坑

1. 为什么用邻接矩阵入门图的存储

不管你是正在啃数据结构期末考试的大二学生，还是准备考研刷题的准研究生，肯定都被图这个章节卡过那么一下。图的存储方式那么多——邻接矩阵、邻接表、十字链表、邻接多重表——第一次接触时确实容易一头雾水。我自己的感受是，邻接矩阵是最适合用来打通图论思路的存储结构，因为它把"顶点之间的关系"直接摊开成一张二维表格，看一眼矩阵就能读懂整张图，代码也几乎没有什么弯弯绕绕。

邻接矩阵的思路说白了就一句话：用一个一维数组存放所有顶点信息，再用一个二维数组存放任意两个顶点之间是否有边。假设图里有 n 个顶点，那就准备一个 n×n 的矩阵，matrix[i][j]的值表示顶点 i 到顶点 j 的边关系。对于不带权的图，1 表示有边，0 表示没边；对于带权图（也叫网），矩阵元素直接存权值，没有直达边的地方用一个足够大的"无穷大"值占位。

这套设计的最大优势在于直观和随机访问高效。你想判断两个顶点之间有没有边？直接if (matrix[i][j] != 0)一次查找就能出结果，时间复杂度是 O(1)。这在后面学习图的遍历、最短路径、最小生成树这些算法时特别能体现价值，因为很多经典算法的基础操作恰恰就是"反复查某两个顶点是否连通"。Prim 算法、Dijkstra 算法在邻接矩阵上的实现逻辑非常直白，就是利用了这种 O(1) 查询的优势。

当然，邻接矩阵的短板也很突出——空间复杂度是 O(n²)。如果图比较稀疏（边数很少），大量矩阵元素都是 0，白占空间不说，遍历矩阵也浪费时间。所以工程场景里更多用邻接表，但教学场景、算法竞赛中数据规模可控的情况下，邻接矩阵依然是不可替代的入门首选。这篇内容就围绕"图邻接矩阵的创建"展开，从结构体定义到完整创建代码，再把容易踩的坑挨个说清楚，适合正在学数据结构的人参考，考前突击也够用。

2. 邻接矩阵的核心数据结构定义

2.1 两条存储线：顶点数组与边矩阵

写代码之前，先理清楚邻接矩阵在内存中到底是怎么组织数据的。它由两条存储线构成：

• 顶点表：一个一维数组，下标对应顶点编号，存储顶点本身的信息。比如顶点类型 char 可以存字符 A、B、C；如果图表达的是交通网络，顶点类型也可以是城市编号之类。
• 边表：一个二维数组，两个下标分别对应起点和终点，存储边的关系。矩阵行号代表起点、列号代表终点，edges[i][j]就是顶点 i 到顶点 j 的关系值。

这个设计可以类比成Excel表格：行是一个城市列表，列是同一个城市列表，表格每个格子就填"这两个城市之间有没有直飞航班"，或者填"航班飞行时间是多少分钟"。行列完全一一对应，查起来特别快。

2.2 结构体定义与字段含义解析

教材和实际项目中常见的定义方式是这样的：

#define MaxVertexNum 100 typedef char VertexType; // 顶点类型，按需修改 typedef int EdgeType; // 边上的权值类型，按需修改 typedef struct { VertexType vexs[MaxVertexNum]; // 顶点表 EdgeType edges[MaxVertexNum][MaxVertexNum]; // 邻接矩阵（边表） int vexnum, arcnum; // 当前顶点数和边数 } MGraph;

这里每一个字段都不能少，也不是随便写的。vexs是一维数组，存放顶点名；edges是二维数组，存放边关系；vexnum和arcnum必须记住当前规模，否则后面遍历、打印、读边信息都没有边界可依。

关于顶点类型和边类型，建议用typedef定义别名而不是直接用 char 和 int。这样做的直接好处是改类型只动一行。如果哪天真要做一个顶点是整数编号、边上带实数权重的图，把两个 typedef 换掉就行，函数签名和逻辑代码完全不用动。我见过不少同学把类型写死，后面换需求时到处改，非常痛苦。

2.3 两种典型定义路线的取舍

结构体定义之后，紧接着面临一个现实选择：用固定大小的静态数组还是动态分配空间？

静态数组（上面的写法）适合教学、考试和规模已知的场景，优点是代码简单、不用考虑内存释放问题，编译器直接分配一块连续空间。缺点是顶点数超过 MaxVertexNum 就无能为力。

动态分配适合做课程设计、实际项目，顶点数由用户输入决定，用 malloc 按需分配：

typedef struct { VertexType *vexs; EdgeType **edges; int vexnum, arcnum; } MGraph; void InitGraph(MGraph *G, int n) { G->vexnum = n; G->vexs = (VertexType *)malloc(n * sizeof(VertexType)); G->edges = (EdgeType **)malloc(n * sizeof(EdgeType *)); for (int i = 0; i < n; i++) { G->edges[i] = (EdgeType *)malloc(n * sizeof(EdgeType)); } }

这两种方案各有适用场景。如果目的是彻底搞懂原理，先用静态数组跑通逻辑，再花时间改成动态版本，这样你对指针和二级指针的理解也会更扎实。我自己最初练习时是静态版本和动态版本各写了一版，对比之后才真正理解"数组下标访问"和"指针偏移访问"的关系。

2.4 矩阵初始化：0 与无穷大的抉择

初始化矩阵这一步很多人会掉坑。无向图、有向图这种不带权图，矩阵元素只表示"是否有边"，统一初始化为 0 即可。但**带权图（网）**不能初始化为 0，因为 0 本身可能就是一个合法权值。比如边权代表费用时，0 元的边是真实存在的。正确的做法是把矩阵所有元素初始化为一个足够大的"无穷大"值：

#define INFINITY 65535

这也是为什么网的问题里打印矩阵时看到一堆大数字的原因，那不是在显示边权，而是在告诉你"这两个顶点之间没有直接通路"。65535 这个值在 int 范围内足够大，同时在做加法运算时不容易溢出，是教材里常用的占位常量。

3. 完整创建流程与核心代码实现

3.1 创建函数的主流程设计

创建邻接矩阵，本质上是"填一张二维表"的过程。完整流程分成四步：

1. 输入图的顶点数和边数，写入结构体。
2. 输入每个顶点的信息，写入一维顶点数组。
3. 把二维矩阵初始化为默认值（0 或 INFINITY）。
4. 逐条读入边信息，把对应矩阵位置写成 1（不带权）或权值（带权）。

这个顺序不能乱。尤其是第 3 步必须在读边信息之前完成，否则旧内存中的脏数据会残留，矩阵出现莫名其妙的随机的数字。我之前带过的一个学生，运行程序后打印矩阵，里面全是类似 32767、-859423 这种数字，就是因为共用体与局部变量未清理导致的读内存垃圾，初始化这一步直接跳过没写。

3.2 无向图创建完整代码

无向图的特点是边没有方向，顶点 A 和顶点 B 之间有边，那么edges[i][j]和edges[j][i]必须都为 1。这一步最容易漏，只赋值一边就会导致矩阵不对称，后续遍历、求度全错。

#include <stdio.h> #define MaxVertexNum 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MaxVertexNum]; EdgeType edges[MaxVertexNum][MaxVertexNum]; int vexnum, arcnum; } MGraph; void CreateMGraph(MGraph *G) { int i, j, k; printf("请输入顶点数和边数："); scanf("%d%d", &G->vexnum, &G->arcnum); // 读入顶点信息 for (i = 0; i < G->vexnum; i++) { printf("请输入第%d个顶点的信息：", i + 1); scanf(" %c", &G->vexs[i]); } // 初始化邻接矩阵 for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->edges[i][j] = 0; } } // 读入边信息，无向图需要对称赋值 for (k = 0; k < G->arcnum; k++) { printf("请输入边(Vi, Vj)的两个顶点下标（0开始）："); scanf("%d%d", &i, &j); G->edges[i][j] = 1; G->edges[j][i] = 1; } }

3.3 有向图与网的差异处理

把上面的代码稍作改动，就能支持不同图类型。

有向图的边有方向，<i, j>表示从 i 指向 j，只有一处赋值：

G->edges[i][j] = 1;

没有edges[j][i] = 1那一行。这也是有向图的邻接矩阵大多不是对称矩阵的由来。

对于带权的网，需要额外输入权值 w，而且矩阵初始化要用 INFINITY 而不是 0：

#define INFINITY 65535 void CreateMGraph_Net(MGraph *G) { int i, j, k, w; printf("请输入顶点数和边数："); scanf("%d%d", &G->vexnum, &G->arcnum); for (i = 0; i < G->vexnum; i++) { printf("请输入第%d个顶点的信息：", i + 1); scanf(" %c", &G->vexs[i]); } for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { G->edges[i][j] = INFINITY; } } for (k = 0; k < G->arcnum; k++) { printf("请输入边(Vi, Vj)的下标和权值w："); scanf("%d%d%d", &i, &j, &w); G->edges[i][j] = w; G->edges[j][i] = w; // 无向网需要对称赋值 } }

这三个版本的差异并不多，核心就在两个地方：矩阵初始化的默认值、是否需要对称赋值。搞懂了这两条规则，任何变体都能自己写出来。

3.4 打印函数与矩阵展示

光把矩阵创建出来还不够，必须有个打印函数直观展示结果。打印时把顶点名也带上，形成带行列标签的表格效果：

void PrintMGraph(MGraph G) { int i, j; printf("\n邻接矩阵如下：\n"); printf(" "); for (i = 0; i < G.vexnum; i++) { printf("%4c", G.vexs[i]); } printf("\n"); for (i = 0; i < G.vexnum; i++) { printf("%2c ", G.vexs[i]); for (j = 0; j < G.vexnum; j++) { if (G.edges[i][j] == INFINITY) { printf("%4s", "∞"); } else { printf("%4d", G.edges[i][j]); } } printf("\n"); } }

注意到打印函数里对 INFINITY 做了特殊判断，输出 ∞ 符号而不是 65535 这种大数字，这样矩阵一眼就能看出拓扑结构。这个细节很实用，调试时可比盯着满屏的 65535 舒服多了。

3.5 主函数测试与运行效果

完整的主函数如下：

int main() { MGraph G; CreateMGraph(&G); PrintMGraph(G); return 0; }

用一个小例子测试。输入 4 个顶点 A、B、C、D，5 条边：

请输入顶点数和边数：4 5 请输入第1个顶点的信息：A 请输入第2个顶点的信息：B 请输入第3个顶点的信息：C 请输入第4个顶点的信息：D 请输入边(Vi, Vj)的两个顶点下标（0开始）：0 1 请输入边(Vi, Vj)的两个顶点下标（0开始）：0 2 请输入边(Vi, Vj)的两个顶点下标（0开始）：0 3 请输入边(Vi, Vj)的两个顶点下标（0开始）：1 2 请输入边(Vi, Vj)的两个顶点下标（0开始）：2 3

打印结果应该是：

A B C D A 0 1 1 1 B 1 0 1 0 C 1 1 0 1 D 1 0 1 0

从矩阵看，A 和所有顶点都相连，B 和 D 之间没有直接边，这和图数据完全吻合。

3.6 复杂度与空间消耗分析

创建过程的时间主要花在两层循环初始化和逐边读入上。初始化矩阵是 n² 次操作，读边是 e 次操作，总时间复杂度为 O(n² + e)，而 n² 这一项通常占主导。空间复杂度无论边多少都是 O(n²)，因为矩阵始终要保存完整。

这就意味着顶点数 n 变大时，内存占用按平方速度增长。n = 100 时数组占 1 万格，完全无压力；n = 10000 时就要占 1 亿格，一个 int 占 4 字节就是 400MB，直接把程序干崩溃。所以邻接矩阵只适合顶点数适中、图比较稠密的场景。

4. 常见问题与排查技巧实录

4.1 问题速查表

4.2 scanf 输入缓冲区的坑

这类问题在 C 语言里太常见了。执行scanf("%d%d", &n, &m)之后，按回车键产生的换行符残留在输入缓冲区里。紧接着执行scanf("%c", &G->vexs[i])时，%c 格式会直接读入那个换行符，结果顶点信息还没等用户输入就被"吃掉"了。

解决方法是格式串里加空格——scanf(" %c", &G->vexs[i])。前面的空格会跳过所有空白字符（包括回车、空格、制表符），这样就能正确读到用户输入的实际字符。这个细节在考试和面试手写代码时经常被考察，重要程度不亚于算法本身的正确性。

4.3 矩阵初始化错误引发的连锁反应

之前调一个模拟项目时，邻接矩阵没有初始化就直接读边，初始化那一步完全被注释掉了。程序运行后打印矩阵，输出的数字五花八门，还有负数。排查了半天才发现是局部变量在栈上分配的空间里残留了之前函数调用的数据。这类脏数据问题尤其隐蔽，因为它不是每次都崩，而是忽对忽错。

所以有一个经验：写完矩阵创建函数，先打印一遍初始化的结果，再读边数据。分两步验证，可以快速定位是初始化的问题还是读入的问题。做一个 2×2 的最小样例验证边界情况，比上来直接测大图更快找到问题。

4.4 顶点编号从 0 还是 1 开始

很多教材习惯用 1 到 n 编号顶点，代码里输入的边就是1 2、2 3。但如果数组下标从 0 开始，直接拿 1 当索引就会越界至少不匹配，边信息全部偏一位。两种方案都可行，但必须统一。我倾向于全部从 0 开始，数组天然适配，循环遍历也更顺手。如果非要按 1 编号的输入格式，就在赋值前做一个i--; j--;的转换，这也是比较常见的处理方式。

5. 邻接矩阵的进阶应用：从创建走向图算法

5.1 用矩阵求顶点度

创建完矩阵后，第一个立刻能上手的操作就是求顶点的度。无向图中顶点 i 的度就是矩阵第 i 行非零元素的个数，因为每一条与 i 相连的边都会在edges[i][j]位置留下一个 1 或权值：

int Degree(MGraph G, int v) { int count = 0; for (int j = 0; j < G.vexnum; j++) { if (G.edges[v][j] != 0 && G.edges[v][j] != INFINITY) { count++; } } return count; }

有向图中要分入度和出度：出度查第 v 行，入度查第 v 列。这些操作在邻接矩阵上都很好写，因为行和列天然对应着出边和入边。

5.2 DFS 和 BFS 遍历怎么用矩阵

深度优先遍历（DFS）和广度优先遍历（BFS）是图论算法的基础，邻接矩阵负责给它们提供"找到下一个邻接点"的能力。DFS 递归访问顶点 i 后，在矩阵第 i 行从第 0 列扫到第 n-1 列，遇到不为 0 且未访问过的顶点 j 就递归进入。BFS 类似，但用队列配合矩阵逐层扩展。

用邻接矩阵实现遍历的好处是代码很直接，不用维护复杂的邻接链表指针结构。时间复杂度都是 O(n²)，因为每个顶点的每一列都要扫描一遍。

5.3 从矩阵看最短路径和最小生成树

带权邻接矩阵是 Dijkstra 算法和 Floyd 算法的直接数据来源。Dijkstra 算法每次从当前未确定最短路径的顶点里选出 dist 最小的，然后扫描矩阵对应行更新邻接点的 dist。Floyd 算法更依赖矩阵，直接在矩阵上做三重循环更新最短路径：

for (k = 0; k < n; k++) for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];

Prim 算法生成最小生成树时，也是维护一个 lowcost 数组，每轮从矩阵里找当前顶点到未访问顶点的最小边权。这些算法在邻接矩阵上的实现都是教科书级别，学会矩阵创建之后，后面学起来会顺畅很多。

5.4 什么时候应该换成邻接表

邻接矩阵虽好，但也要理智看待。如果一个图有 1000 个顶点却只有 2000 条边，矩阵要开 100 万格，其中 99.8% 都是 0，白白浪费内存。这种情况下邻接表只存存在的边，每条边用一个链表节点表示，空间效率高得多。

判断标准很简单：e（边数）接近 n² 时用邻接矩阵，e 远小于 n² 时用邻接表。考试时如果题目没指定，先数一下边密度再选结构，这也是考察点之一。

在学数据结构这件事上，我个人的经验是：邻接矩阵一定要亲手写一遍完整的创建过程，别只看代码。第一次写不出来的地方，往往就是理解有漏洞的地方。矩阵初始化的值、对称赋值的来源、下标的起止范围，每一个细节都值得单独推敲一遍。

另外有一个小技巧，调试时可以把打印函数拆成两个版本，一个专门打印矩阵初始值，一个打印最终结果。对比两个输出，就能清楚知道初始化或读边哪一步出了问题。这种"分步验证、对比定位"的思路，比盯着代码干找效率高太多了。

把邻接矩阵的创建和这些衍生操作弄扎实之后，再去看图的遍历、最短路径、拓扑排序这些内容，你会发现它们全都建立在同一张矩阵上，理解起来就是一个层层递进的过程。数据结构的学习就是这么一环扣一环，前面基础打牢了，后面自然走得稳。