1. 图的两大存储方案邻接矩阵与邻接表的选择逻辑说实话每次在PTA上碰到图的题目很多同学的第一反应是直接开干结果往往在存储方式这一步就走错了方向。我自己带过不少准备天梯赛和数据结构课程设计的同学发现一个共同规律存储结构选对了遍历代码写起来顺手调试也快选错了后面全是坑甚至会在DFS递归时被爆栈问题整得怀疑人生。今天这篇不讲虚的就从图的存储和遍历这个地基聊起把PTA上反复出现的考点彻底拆明白。1.1 邻接矩阵什么时候无脑选它邻接矩阵的思路非常朴素——用一个二维数组G[i][j]来记录顶点i和顶点j之间的关系。有边就是1或者权重无边就是0。这个方案最大的优点就是结构简单、代码直白判断任意两个顶点之间是否有边只需要O(1)时间。但它的代价也相当显眼空间复杂度是O(V²)其中V是顶点数。这意味着当顶点数达到10000时单单存储一个int型的二维数组就需要约400MB内存10000×10000×4字节这在PTA的OJ判题环境下几乎是必炸的。我的个人经验是在PTA上遇到以下情况时优先考虑邻接矩阵顶点数V较小通常在1000以内比如V≤500时邻接矩阵完全无压力题目中需要频繁判断两点之间是否有边比如最短路径类问题图比较稠密边的数量接近V²的量级。举个典型例子PTA里经常出现的图着色问题或者判断连通性的简单版本顶点数通常控制在100以内这时候用邻接矩阵写起来非常舒服#include cstdio #include cstring #define MAXV 105 int G[MAXV][MAXV]; int vis[MAXV]; void DFS(int u, int n) { vis[u] 1; printf( %d, u); for (int v 1; v n; v) { if (G[u][v] !vis[v]) { DFS(v, n); } } } int main() { int n, m; scanf(%d %d, n, m); memset(G, 0, sizeof(G)); memset(vis, 0, sizeof(vis)); for (int i 0; i m; i) { int u, v; scanf(%d %d, u, v); G[u][v] G[v][u] 1; // 无向图 } for (int i 1; i n; i) { if (!vis[i]) { DFS(i, n); printf(\n); } } return 0; }这里有个非常实用的细节如果题目中顶点编号是从1开始而不是从0开始我通常就直接把数组开到MAXV 5然后从1开始循环省去下标减一的麻烦也能避免因为忘记转换而出现的越界错误。这个习惯看起来小但真能帮你避开不少低级扣分。1.2 邻接表稀疏图的必选项当顶点数达到10⁵级别边数只有10⁵到10⁶时邻接矩阵就完全不可行了必须改用邻接表。邻接表的本质是对每个顶点维护一个链表或者vector里面存放所有与该顶点直接相连的邻居节点。空间复杂度降到O(VE)这也是PTA绝大多数图论题目的标准做法。在C里最推荐的方式是用vectorint adj[MAXV]或者vectorvectorint adj原因很简单vector帮你管理内存不需要手动写链表节点也不容易发生指针错误。我在PTA上写邻接表遍历的模板大致是这样#include cstdio #include vector #include queue #include algorithm using namespace std; const int MAXV 100005; vectorint adj[MAXV]; int vis[MAXV]; void DFS(int u) { vis[u] 1; printf( %d, u); // 按照编号从小到大访问 sort(adj[u].begin(), adj[u].end()); for (int v : adj[u]) { if (!vis[v]) DFS(v); } } void BFS(int start) { queueint q; q.push(start); vis[start] 1; while (!q.empty()) { int u q.front(); q.pop(); printf( %d, u); for (int v : adj[u]) { if (!vis[v]) { vis[v] 1; q.push(v); } } } }注意上面代码里我对邻接表做了sort这不是多余的。PTA许多遍历题目的输出要求按编号递增顺序访问邻接点如果输入边的时候没有按顺序就必须在遍历前排序。这个排序动作看起来增加了O(E log E)的复杂度但在大多数题目的数据范围内完全可行而且能直接避免输出顺序错误导致的WA。2. 深度优先遍历递归思想在OJ里的真实面貌2.1 DFS与二叉树的前序遍历是一家人很多同学在学DFS时觉得图里的DFS很抽象但如果在学二叉树时理解透彻了先序遍历根左右图里的DFS其实只是把二叉树中每个节点最多有两个孩子扩展成了每个节点可以有任意多个邻居。我之前在博客里反复强调过DFS本质上是沿着一条路走到黑走不动了再退回来的策略。在递归实现中系统栈帮我们维护了路径回溯的过程在显式栈实现中自己压栈的元素则记录了下一步该从哪里继续。PTA里常见的DFS题型包括列出连通集判断是否存在环拓扑排序的DFS实现等。其中列出连通集题目算是DFS最直白的应用它要求从编号最小的顶点开始深度优先搜索并输出所有连通分量。这个题需要注意的点在于连通分量之间是独立的遍历完一个连通分量后还要循环去找下一个未被访问的顶点直到所有顶点都被访问过。2.2 递归的代价从爆栈到显式栈我在PTA上曾经遇到过一道遍历题数据范围写到V50000递归DFS直接导致栈溢出程序运行到一半就异常终止。那次经历给我留下了深刻印象OJ环境的栈大小通常是有限的往往在8MB左右深层递归很容易秒爆。解决方案有两种一是增大递归深度限制某些OJ支持通过编译器参数调整但PTA上未必可靠二是将递归DFS改为显式栈的迭代DFS。迭代版代码如下void DFS_iter(int start) { stackint st; st.push(start); vis[start] 1; while (!st.empty()) { int u st.top(); st.pop(); printf( %d, u); for (int v : adj[u]) { if (!vis[v]) { vis[v] 1; st.push(v); } } } }不过这里要提醒一下显式栈版本的DFS和递归版本的DFS在访问顺序上可能有差异。递归版本是入栈前就被访问而显式栈版本如果只在pop时输出就变成了类似后进先出首次扩展的顺序有时会和题目预期的输出顺序不一致。如果遇到顺序WA可以在push时标记vis但用另一个数组记录访问顺序也可以把邻接点逆序压栈确保pop出来的顺序与递归版本一致。这个细节非常值得在调试过程中专门验证不能想当然。这里提醒一下新手不要一上来就写递归因为递归的思维负担最小但如果题目的V大到10⁵以上一定要有意识地评估递归深度。可以先提交一次递归版本试探如果收到段错误或者非零返回再换成显式栈版本。3. 广度优先遍历从队列到层序思维3.1 BFS为什么天然契合最少步数问题BFS广度优先搜索的核心是从起点出发一层一层往外扩散。这个策略恰好满足无权图最短路径的需求第一次访问到某个顶点时经过的边数一定是最少的。所以PTA里六度空间社交网络图中好友关系层数统计等题目本质上都建立在BFS之上。我在之前的专栏里不止一次写过BFS实现的关键是队列。起点入队队首出队时把它的所有未访问邻居入队如此往复直到队列为空。因为队列的FIFO特性同深度的顶点一定会先于更深层的顶点被访问这也是层序直觉的来源。用BFS遍历时有几点经验值得分享入队的同时就要标记访问否则同一个节点可能会被多个邻居重复入队造成死循环或者输出重复如果需要输出层数可以在队列里同时保存节点和层级信息也可以用当前层计数的方式分层统计对于无向图BFS和DFS一样同样需要在遍历完后检查所有顶点确保所有连通分量都被覆盖。3.2 邻接表BFS的PTA格式细节PTA对BFS输出的格式卡得非常严格行尾不能有多余空格每个顶点的访问顺序必须完全正确。我在列出连通集题目中踩过一次坑因为忘了对邻接表排序输出的访问顺序和题目要求不一致白白浪费了三次提交。正确的做法是在BFS启动之前先对每个顶点的邻接表做一次排序。如果边的输入顺序已经是升序这一步可以省略但如果输入是乱序的不做排序必错。另外一个输出细节是第一个数前没有空格后续数前有空格这个用标志变量控制bool first true; void print(int x) { if (first) { printf(%d, x); first false; } else printf( %d, x); }这个方法比起先拼字符串再去除末尾空格要干净得多也避免了字符串操作的额外开销。4. PTA判题视角输入输出格式与常见扣分陷阱4.1 理解OJ的黑盒测试本质PTA的判题方式和其他在线评测系统一样都是黑盒测试你的程序读取标准输入产生标准输出然后用一组测试数据的预期输出和你的输出做逐字节比对。这意味着任何多余的字符、缺失的空格、错误的换行都会导致WA。我特别想建议初学者做一件事在本地调试时一定要自己构造至少三组测试数据分别覆盖一个顶点的极端情况非连通图顶点编号从1开始这三种典型场景。不要只在样例数据上通过了就提交因为PTA的隐藏测试数据往往比样例刁钻得多。举个例子对于图遍历题很多同学会忽略图可能完全不连通这个前提导致遍历只处理了第一个连通分量后面的顶点完全没有输出。我在代码里总是习惯在读完所有顶点之后用一层for循环把所有顶点都扫一遍每遇到未访问顶点就启动一次DFS或BFS这样无论图连不连通都能完整覆盖。4.2 几个极易踩中的隐藏扣分点我梳理了一下自己在PTA图遍历题上踩过和帮别人排查过的常见错误列个表供参考问题现象根本原因解决办法输出顺序与样例不符邻接表未按编号排序在遍历前对每个顶点的邻接表排序程序运行超时使用邻接矩阵而顶点数过大改为邻接表存储降低空间与遍历复杂度找不到孤立点没有在主函数里循环访问所有顶点外层加一层遍历检查所有未访问顶点依次作为起点输出末尾多空格格式控制不当使用标志变量控制空格输出段错误递归深度过大或数组下标越界改用迭代DFS检查数组大小及顶点编号边界重复输出节点被多个父节点访问时未及时标记在入队/入栈时立刻标记已访问这个表格里的前四项几乎覆盖了PTA图遍历题80%的WA原因。尤其是末尾空格的问题很多同学觉得多一个空格无伤大雅但在OJ的逐字节比对机制下这就是实打实的错误。这里再补充一点关于邻接矩阵初始化的建议如果是多组测试数据的题目每处理完一组数据后一定要把vis数组和邻接矩阵清零。用memset最快但要注意memset是按字节操作的对int数组清0没问题如果要重置成其他值就得手动循环了。我自己习惯在每组数据的开头调用一次memset避免上一组数据残留的访问标记影响当前结果。5. 从存储到遍历一道完整题目的设计与思考5.1 还原列出连通集的完整解题链路以PTA的经典题列出连通集为例完整走一遍从读题到AC的过程。这道题的要求是给定一个无向图要求先输出DFS的结果再输出BFS的结果每个连通分量输出一行且每个连通分量从编号最小的顶点开始。拿到题目后我建议先画个图把样例输入对应的无向图在纸上画出来然后手写一遍DFS和BFS的预期输出。这个过程看似多余却能帮你把递归/队列的抽象流动具象化是排查逻辑错误最快的手段。核心代码结构如下// 主函数中的连通分量循环 for (int i 0; i n; i) { if (!vis[i]) { first true; DFS(i); printf(\n); } } memset(vis, 0, sizeof(vis)); for (int i 0; i n; i) { if (!vis[i]) { first true; BFS(i); printf(\n); } }这段代码里有几个设计意图值得说明先用DFS遍历所有连通分量输出完毕后再统一重置vis数组确保BFS阶段从零开始不会受到DFS阶段标记的干扰每个连通分量的内部输出前都重置first标志确保换行和空格格式正确外层循环从最小的顶点编号开始天然满足从编号最小的顶点开始这一题目要求。5.2 测试数据自检与常见失误的自我排查AC代码不是一次写出来的我通常会准备下面五组数据来验证只有一个顶点的图输入1 0预期输出只有一行0两个顶点无边输入2 0预期输出两行分别是0和1两个顶点一条边输入2 1 0 1预期输出各一行包含两个顶点三个顶点构成一个三角形预期DFS/BFS输出顺序一致都是0 1 2普通非连通图包含两个连通分量每个分量的大小不同验证循环遍历的正确性。如果这五组数据全部通过基本上这道题的隐藏用例也能过掉七八成了。剩余的边界问题比如顶点编号从1开始只需把数组和循环起点调整即可。在调试过程中我还习惯把DFS和BFS的执行过程打印到本地终端上包括当前访问的顶点当前顶点有哪些邻居哪些邻居已经被访问过。这样能直观看到递归和队列的变化比起单纯盯着代码找错要高效得多。当然这些调试用的打印在提交前必须删掉或者注释掉否则输出格式会多出一堆信息。5.3 从一道题到一类题举一反三的扩展图的存储和遍历是后续所有图算法的基础掌握了这两件事后面的最短路径、最小生成树、拓扑排序、连通分量求解都是在这个地基上盖楼。比如PTA里的六度空间题就是在BFS的基础上额外统计层数不超过6的节点占比图着色问题是要基于邻接矩阵检查每条边的两端颜色是否不同关键活动题则是在拓扑排序的基础上加入事件最早/最晚发生时间的计算。如果存储和遍历写得顺手这些题的核心逻辑其实都不会太难。我的体会是做题不要贪多关键是吃透每一道题背后的数据结构和算法设计思路。把图的两种存储方式、DFS/BFS的两种遍历策略以及它们在PTA判题环境下的各种细节全部搞清楚比盲目刷十道同类型的题收获更大。图这块知识是典型的会者不难难者不会一旦你打通了存储和遍历这个关键的任督二脉后面遇到再复杂的图论题至少不会在起步阶段就卡住。