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出发到不了Adebug半天。所以写无向图的时候脑子里要时刻绷着对称这根弦。如果是带权图对称赋值变成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(ne)。所以选存储结构要看图的稠密程度。稠密图边数接近n²用邻接矩阵划算稀疏图用邻接表。实验题里顶点数一般不大邻接矩阵够用而且写起来快。对比项邻接矩阵邻接表空间复杂度O(n²)O(ne)判断两点是否有边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分不多但它是图论这一章的敲门砖值得认真对待。