1. 从一道20分实验题说起：邻接矩阵建无向图到底在考什么
很多人第一次看到"采用邻接矩阵表示法创建无向图"这个实验题，第一反应是"不就是开个二维数组吗"。真动手写的时候才发现，20分的题能扣掉一半——顶点信息怎么存、边权怎么处理、输入格式怎么对齐、对称位置怎么赋值，每一个细节都能让程序跑出莫名其妙的结果。我带过几届数据结构实验课，这道题是典型的"看着简单、写起来到处漏"的题型。
先把场景说清楚。这道题属于图论存储结构的基础实验，核心目标是让你用邻接矩阵这种存储方式，把一个无向图从输入数据变成内存里的数据结构。无向图的特点是边没有方向，顶点A到顶点B有边，等价于顶点B到顶点A有边。这个"对称性"是整道题的关键，也是后面所有操作的根基。
适合谁来参考这篇内容？如果你是正在做数据结构实验的学生，或者刚接触图论、想搞明白邻接矩阵到底怎么落地的人，这篇会从设计思路、代码实现、输入处理、常见错误四个层面把它拆干净。如果你已经写过有向图的邻接矩阵，那这篇的重点在于"无向图多出来的那一步对称赋值"以及"顶点表和矩阵的配合关系"。
我先把结论摆出来：邻接矩阵建无向图，本质上就三件事——存顶点、开矩阵、填边。但每一件事都有坑。顶点存哪里、矩阵初始化成什么值、边的两个方向怎么填、带权和不带权的处理差异，这些才是拿满20分的关键。下面我按实际写代码的顺序，一层一层往下拆。
2. 邻接矩阵的存储设计：顶点表与边矩阵如何配合
2.1 为什么需要"顶点表+矩阵"两套结构
邻接矩阵本身只是一个二维数组，它只能表达"第i个顶点和第j个顶点之间有没有边"。但问题来了：数组下标是0、1、2这样的数字，而实际图里的顶点可能是字符'A'、'B'、'C'，也可能是字符串"北京"、"上海"。所以光有矩阵不够，必须再配一个顶点表，用来建立"下标"和"实际顶点信息"之间的映射。
这就是邻接矩阵存储法的标准结构：一个一维数组存顶点，一个二维数组存边。两者通过下标关联——顶点表里第i个位置的顶点，就对应矩阵的第i行第i列。这个设计思路和哈希表有点像，下标是key，顶点信息是value，只不过这里的key是连续整数，不需要哈希函数。
我见过有同学图省事，直接把顶点当成矩阵下标用，比如顶点是'A'就用matrix['A']['B']。C语言里字符确实能当数组下标（本质是ASCII码），但一旦顶点是字符串或者编号不连续，这套就崩了。所以老老实实建顶点表，是工程上更稳的做法。
2.2 顶点表该存什么
顶点表存的内容取决于题目要求。最简情况下，顶点就是一个字符或者一个整数编号，那顶点表就是一个char数组或int数组。如果顶点还带其他属性（比如城市名、权重、颜色），那就得定义一个结构体，顶点表变成结构体数组。
#define MAXVEX 100 // 最大顶点数 typedef struct { char vexs[MAXVEX]; // 顶点表，存顶点信息 int arc[MAXVEX][MAXVEX]; // 邻接矩阵，存边 int numVertexes; // 当前顶点数 int numEdges; // 当前边数 } MGraph;这个结构体是邻接矩阵的经典定义。vexs是顶点表，arc是边矩阵，后面两个字段记录实际的顶点数和边数。为什么要单独记数量？因为数组开的是MAXVEX大小，但实际可能只用了5个顶点，遍历的时候必须知道真实边界，不能傻乎乎遍历100个。
提示：MAXVEX这个上限要根据题目数据范围来定。开太小会数组越界，开太大浪费内存。一般实验题顶点数不会超过100，开100足够。如果是竞赛题，看清楚数据范围再定。
2.3 矩阵里到底填什么值
这是新手最容易迷糊的地方。邻接矩阵的每个元素arc[i][j]表示顶点i到顶点j的关系，填什么值分两种情况：
不带权的图：填0或1。1表示有边，0表示无边。有些实现里用1表示无边、0表示有边，也能跑，但不符合直觉，容易把自己绕晕，不建议。
带权的图：填权值。有边就填具体权重，无边要填一个"无穷大"的标记。这个无穷大通常用INF宏定义，比如#define INF 65535或者#define INF 0x3f3f3f3f。为什么不用INT_MAX？因为后面做最短路径之类的运算时，INT_MAX加上一个数会溢出变成负数，而0x3f3f3f3f加上一个不太大的数还在int范围内，这是竞赛圈的老经验。
#define INF 0x3f3f3f3f对于无向图，矩阵还有一个铁律：它一定是对称矩阵。arc[i][j] == arc[j][i]永远成立。这个性质后面会反复用到，也是检查自己代码对不对的一把尺子。
3. 创建无向图的完整流程与对称赋值的关键细节
3.1 整体流程拆解
创建无向图的标准流程分四步，我按实际代码顺序列出来：
- 输入顶点数和边数，存进
numVertexes和numEdges。 - 输入顶点信息，逐个填进
vexs数组。 - 初始化矩阵，把所有元素置为"无边"状态（不带权置0，带权置INF）。
- 循环输入每条边，对每条边
(u, v)，在矩阵里填两个位置：arc[u][v]和arc[v][u]。
第三步的初始化经常被忽略。如果你用全局数组或者静态数组，默认就是0，不带权的图可以省这一步。但如果是局部数组，里面是随机垃圾值，不初始化直接填边，结果就是矩阵里混着一堆莫名其妙的数。带权的图更必须初始化，因为无边的地方要明确标成INF。
3.2 对称赋值：无向图的灵魂操作
有向图填边只填一个位置：arc[u][v] = 1。无向图必须填两个：arc[u][v] = 1和arc[v][u] = 1。这一步就是"对称赋值"，是无向图和有向图在存储上唯一的本质区别。
// 输入每条边 for (int k = 0; k < g.numEdges; k++) { int i, j; scanf("%d %d", &i, &j); // 输入边的两个顶点下标 g.arc[i][j] = 1; g.arc[j][i] = 1; // 无向图的关键：反向也要赋值 }看起来简单，但坑就在这。我见过太多人只写了arc[i][j] = 1，忘了反向那一句，程序跑出来是个"有向图"，后面做遍历的时候发现从B出发到不了A，debug半天。所以写无向图的时候，脑子里要时刻绷着"对称"这根弦。
如果是带权图，对称赋值变成：
g.arc[i][j] = w; g.arc[j][i] = w; // 无向图，两个方向的权值相同注意权值w在两个方向是一样的，因为无向图的边没有方向，权重自然也不分方向。
3.3 顶点下标从0还是从1开始
这个问题看似小，实则影响全局。如果顶点下标从0开始，矩阵下标直接用，没问题。如果题目给的顶点编号从1开始（比如顶点1到顶点n），你有两个选择：要么把矩阵也开成1到n（浪费第0行第0列），要么输入时统一减1转成0基下标。
我个人的习惯是内部统一用0基下标，输入的时候如果是1基就减1。这样矩阵不浪费空间，遍历也符合C语言习惯。但要注意，输出的时候如果题目要求1基编号，得记得加回去。这个转换点如果散落在代码各处，很容易漏，建议在输入边的那一步集中处理。
scanf("%d %d", &i, &j); i--; j--; // 统一转成0基下标 g.arc[i][j] = 1; g.arc[j][i] = 1;3.4 完整代码实现
把上面的东西拼起来，一个完整的创建函数长这样：
#include <stdio.h> #define MAXVEX 100 #define INF 0x3f3f3f3f typedef struct { char vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; } MGraph; void CreateMGraph(MGraph *g) { int i, j, k; printf("请输入顶点数和边数："); scanf("%d %d", &g->numVertexes, &g->numEdges); printf("请输入顶点信息："); for (i = 0; i < g->numVertexes; i++) { scanf(" %c", &g->vexs[i]); // 前面的空格吃掉换行符 } // 初始化矩阵 for (i = 0; i < g->numVertexes; i++) { for (j = 0; j < g->numVertexes; j++) { g->arc[i][j] = 0; // 不带权，0表示无边 } } // 输入边 printf("请输入每条边的两个顶点下标："); for (k = 0; k < g->numEdges; k++) { scanf("%d %d", &i, &j); g->arc[i][j] = 1; g->arc[j][i] = 1; // 对称赋值 } }这段代码能跑，但有几个细节值得说。scanf(" %c", ...)里那个空格是故意的，用来跳过前面的空白字符（包括回车），否则读顶点的时候会把上一行的换行符当成顶点读进去。这个坑在字符输入时特别常见。
4. 输入处理与边界情况：那些让程序跑不对的隐形陷阱
4.1 输入格式的三种常见形态
实验题的输入格式千变万化，但归纳起来就三种：
形态一：先给顶点数边数，再给顶点，再给边
5 6 A B C D E 0 1 0 2 1 3 2 3 3 4 1 4这是最标准的格式，按顺序读就行。
形态二：顶点信息省略，直接用编号
5 6 0 1 0 2 ...顶点就是0到4，不需要单独读顶点表，但顶点表还是要建（存编号），只是不用从输入读。
形态三：边用字符表示
5 6 A B A C B D ...这时候要先把字符转成下标。做法是遍历顶点表找到匹配的位置，或者用字符减'A'（如果顶点是连续大写字母）。
// 字符顶点转下标 int LocateVex(MGraph *g, char v) { for (int i = 0; i < g->numVertexes; i++) { if (g->vexs[i] == v) return i; } return -1; // 没找到 }这个LocateVex函数是图操作里的常客，后面做遍历、找邻接点都会用到，建议单独封装。
4.2 自环和重边的处理
自环是指一条边的两个端点是同一个顶点，比如(2, 2)。在无向图里，自环对应矩阵对角线上的元素arc[2][2] = 1。对称赋值的时候，arc[i][j]和arc[j][i]是同一个位置，赋两次也没事，但逻辑上要想清楚题目允不允许自环。
重边是指两个顶点之间有多条边，比如(0,1)输入了两次。邻接矩阵存不下重边——它只能表示"有"或"没有"，第二次输入会把第一次覆盖掉。如果题目要求处理重边（比如取最小权值），那在赋值前要先判断：
if (w < g->arc[i][j]) { // 带权图取较小权 g->arc[i][j] = w; g->arc[j][i] = w; }不带权的图遇到重边，直接覆盖成1就行，结果一样。
4.3 顶点数边数为0的边界
如果输入0 0，表示空图。这时候所有循环都不执行，程序应该正常结束不崩溃。检查一下你的代码：顶点表循环i < 0不执行，矩阵初始化循环也不执行，边循环不执行。没问题。但如果后面有遍历操作，要保证遍历空图不会越界。
还有一种情况是边数为0但顶点数不为0，这叫"零图"，只有孤立顶点没有边。矩阵全是0，也是合法输入。
4.4 输入缓冲区残留问题
这是C语言输入的老大难。scanf读整数时，遇到非数字字符会停下来，把那个字符留在缓冲区里。如果后面紧接着读字符，就会读到这个残留字符。
典型场景：先scanf("%d %d", &n, &m)读顶点数和边数，然后scanf("%c", &ch)读顶点。第二个scanf会读到第一行末尾的回车符，导致顶点读错位。
解决办法有两个：一是在%c前加空格scanf(" %c", &ch)，让scanf自动跳过空白；二是用getchar()手动吃掉回车。我推荐第一种，简洁不易错。
注意：
scanf(" %c", ...)里的空格不是可有可无的，它专门用来跳过任意数量的空白字符（空格、制表符、换行）。这个技巧在处理混合输入时非常有用。
5. 从建图到用图：邻接矩阵的验证与后续操作衔接
5.1 怎么验证建出来的图是对的
代码写完不能只看它不报错就完事，得验证矩阵内容符合预期。最直接的办法是把矩阵打印出来看。
void PrintMatrix(MGraph *g) { printf("邻接矩阵：\n"); for (int i = 0; i < g->numVertexes; i++) { for (int j = 0; j < g->numVertexes; j++) { printf("%d ", g->arc[i][j]); } printf("\n"); } }打印出来之后，对照输入数据检查三件事：一是对角线是不是全0（没有自环的话）；二是矩阵是不是对称的，arc[i][j]和arc[j][i]是否相等；三是每条输入的边对应的位置是不是1。
对称性检查尤其重要，它是无向图的身份证。如果打印出来不对称，那一定是漏了反向赋值。
5.2 邻接矩阵的度计算
建好图之后，最常见的操作是算顶点的度。无向图里，顶点i的度等于矩阵第i行所有元素之和（不带权图）。
int Degree(MGraph *g, int i) { int deg = 0; for (int j = 0; j < g->numVertexes; j++) { deg += g->arc[i][j]; } return deg; }为什么是行和？因为第i行记录的是顶点i和其他所有顶点的连接关系，每有一个1就代表一条边，加起来就是度。带权图的话，行和是"带权度"，物理意义不同，要看题目要求。
这个操作能反过来验证建图正确性：如果某个顶点的度和你手算的不一样，说明边填错了。
5.3 邻接矩阵的优缺点与适用场景
邻接矩阵不是万能的，它有明确的适用边界。
优点：判断两个顶点之间有没有边是O(1)的，直接查arc[i][j]；实现简单，二维数组谁都会用；方便做矩阵运算相关的图算法。
缺点：空间复杂度是O(n²)，n是顶点数。如果图很稀疏（边很少），大量空间浪费在存0上。比如1000个顶点只有10条边，矩阵要开100万个格子，其中99.99%是0。这时候邻接表更合适，空间是O(n+e)。
所以选存储结构要看图的稠密程度。稠密图（边数接近n²）用邻接矩阵划算，稀疏图用邻接表。实验题里顶点数一般不大，邻接矩阵够用，而且写起来快。
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(n²) | O(n+e) |
| 判断两点是否有边 | O(1) | O(度) |
| 找某点所有邻接点 | O(n) | O(度) |
| 适合图类型 | 稠密图 | 稀疏图 |
| 实现难度 | 低 | 中 |
5.4 建图之后能接什么操作
创建图只是第一步，后面通常要接图的遍历。邻接矩阵上的DFS和BFS都好写，因为找邻接点就是扫一行。
DFS的核心是递归加访问标记：
int visited[MAXVEX]; void DFS(MGraph *g, int i) { visited[i] = 1; printf("%c ", g->vexs[i]); for (int j = 0; j < g->numVertexes; j++) { if (g->arc[i][j] == 1 && !visited[j]) { DFS(g, j); } } }BFS用队列，思路类似。这两个遍历都依赖建图时填好的矩阵，所以建图这一步的正确性直接决定后面所有操作的结果。这也是为什么实验题把"创建图"单独拎出来给20分——它是地基。
6. 我踩过的坑和几条实在的经验
6.1 忘记初始化矩阵导致随机值
第一次写这道题的时候，我用的是局部变量MGraph g;，没初始化矩阵就直接填边。结果打印出来一堆奇怪的数字，因为局部数组里是栈上的垃圾值。后来改成先双重循环全部置0，问题消失。这个坑的教训是：只要数组不是全局或静态的，用之前必须显式初始化。全局数组默认全0是C语言的保证，但局部数组没有这个待遇。
6.2 对称赋值漏写反向
这个前面反复强调了，但我还是要再提一次，因为它太容易犯了。尤其是从有向图代码改过来的时候，脑子里还想着"填一个位置就行"，结果无向图跑成了有向图。我的建议是写无向图填边的时候，把两行赋值写在一起，中间不要插其他逻辑，形成肌肉记忆。
6.3 顶点下标转换不统一
有一次题目顶点编号从1开始，我输入边的时候忘了减1，导致矩阵第0行第0列永远是空的，而第n行第n列越界。程序没崩是因为数组开得够大，但结果全错。后来我养成了一个习惯：在输入边的那一步集中做下标转换，转换完立刻赋值，不在中间穿插其他操作。这样转换逻辑只有一处，不会漏。
6.4 字符输入的空白符问题
读顶点字符时被回车符坑过不止一次。scanf("%c")会老老实实读入回车，把它当成一个顶点。解决办法就是加空格scanf(" %c")。这个空格的作用是"跳过任意空白字符"，是C语言scanf的一个特性，很多人不知道。
6.5 关于MAXVEX的取值
实验题一般会给数据范围，比如"顶点数不超过100"，那就#define MAXVEX 100。但要注意，如果顶点数正好是100，数组下标是0到99，开100刚好够。如果题目说"不超过100"但实际可能给100，那开100没问题；如果给101就崩了。保险起见可以开大一点，比如105或110，多几个格子不占多少内存。
6.6 一个提高效率的小技巧
如果你要反复调试建图逻辑，可以把输入重定向到文件，省得每次手动敲一堆数据。
freopen("input.txt", "r", stdin);这样程序从文件读输入，你改数据只改文件就行。调试完把这行注释掉，交作业前记得删。这个技巧在调试复杂输入时特别省时间。
6.7 关于带权图的INF选择
带权图无边的地方要填INF。我推荐用0x3f3f3f3f而不是INT_MAX，原因是后面做加法运算时不会溢出。0x3f3f3f3f大约是10.6亿，两个相加约21亿，还在int的21.4亿范围内。而INT_MAX加任何正数都会溢出成负数，导致比较逻辑出错。这是竞赛圈流传多年的经验值，值得记住。
把这道题吃透，其实不只是学会一个邻接矩阵。它训练的是"数据结构设计"的基本功：怎么用数组表达关系、怎么处理对称性、怎么在输入输出之间做转换、怎么验证结果的正确性。这些能力在后面学邻接表、十字链表、邻接多重表的时候会反复用到。20分不多，但它是图论这一章的敲门砖，值得认真对待。
