先放一个我观察很久的现象身边准备华为OD机试的人刷题列表里堆了一堆字符串、数组、链表、二叉树但一看到“图”字就跳过理由是“感觉很难考得少”。结果真正上了考场难题往往就落在图或者动态规划上前面简单题做完了最后一道题卡半小时起步分数拉不上去非常可惜。这篇就针对“数据结构–图”这个专题按华为OD机试的实际考法来写图的考点到底有哪些、用什么方式建图最稳、每个核心算法怎么做、平时练习根本注意不到但考场上会炸的细节是什么。如果你正在备机试或者单纯想补一下图论这块基础这篇应该能省掉你不少绕路时间。1. 机试里的图长什么样先学会识别“伪装”1.1 三类高频“换皮”描述图论题在机试里有个典型特征题目不会直接告诉你“这是一张图”。最常见的换皮方式是“地理网络”。比如给你N个城市M条道路每条道路有长度问从城市A到城市B的最短通行时间。这就是标准的最短路径问题城市是节点道路是边长度是边权。第二种是“依赖关系”。比如有N个任务某些任务必须等另一些任务完成后才能开始问能否按顺序全部执行。这种说法背后就是拓扑排序任务是节点依赖是边。第三种是“连接关系”。比如N台设备通过若干网线连接问其中两台设备是否连通或者N个人之间存在好友关系问朋友圈分成几块。这对应的是图的遍历和连通性判断用DFS/BFS或并查集都能解决。所以读题的第一步不是急着想算法而是先把“节点”和“边”从题干里翻译出来。我自己的习惯是看到数字N和M又看到一条一条“从u到v”的描述脑子里会自动把它改写成图的输入格式。1.2 图题在整套题中的位置华为OD机试通常是一套几道编程题难度递增。据我了解的情况图相关的题大概率出现在后段的分值题里尤其是“稍复杂的BFS”或“带权最短路径”这类。有些年份也会在中间题里放一个“迷宫最短步数”本质就是无权图BFS套模板就能写。这也意味着一个现实图题属于“会者不难难者不会”的题。你把模板背熟了它就是送分题你没准备在考场现推Dijkstra的优先队列写法大概率推不出来。所以备考时不对图做专项训练等于主动放弃后面的分值大头。1.3 判断是不是图题的三板斧我拿到一道算法题习惯用三个问题做快速归类有没有一批“独立个体”人、城市、任务、状态这些都可以是节点。个体之间有没有“连接关系”路、依赖、好友、跳转这些都可以是边。题目问的是不是“可达性、最短代价、连通数量、执行顺序、是否存在环”三个问题只要有至少两个回答“是”这题基本就是图论题。这时候别管它包装成什么样直接往图的模板上靠。判断窗口期越短后面写代码越稳。最怕的是读完题还在纠结“这题考的是贪心还是搜索”等想明白时间已经浪费一半了。2. 建图方式的选择邻接矩阵还是邻接表2.1 两种方式的底层差别图建不好后面全是坑。机试里建图方式无非两种邻接矩阵和邻接表。邻接矩阵说白了就是一张二维表格。graph[u][v]表示从u到v有没有边有边就存边权没边就存一个无穷大。生活化理解就是一张“全班通讯录表格”每个人名占一行一列认识就打个勾。好处是判断任意两点是否直接相连复杂度是O(1)写起来也简单坏处是空间是O(n²)当n稍微大一点比如n10000光开二维表就要1亿个格子直接内存超限。邻接表则更像“每个人的私人通讯录”每个节点只记录它认识的邻居。用Listint[][]或者ListListint[]实现每条边只在对应节点的列表里出现一次。空间是O(nm)其中m是边数适合更常见的稀疏图。代价是判断两点是否直连需要遍历列表不如矩阵快。2.2 按数据规模做选择根据我个人刷题和参加机试的经验华为OD机试的图题数据范围有一定规律节点数N经常在几百到几千偶有上万的情况。面对不同规模我的选法是这样场景推荐方案原因N ≤ 100边接近满邻接矩阵代码最短遍历也直观N ≤ 1000边数少邻接表遍历邻居快空间省N ≤ 2000稠密图邻接矩阵内存大概16MB左右还可以接受N 2000邻接表矩阵内存成平方级增长风险大涉及Dijkstra最短路邻接表堆优化版需要频繁遍历邻居只需判断两点是否连通邻接矩阵如果N允许O(1)判断很香这里有个细节如果你已经决定用BFS/DFS那么无论矩阵还是表都能跑。但如果后面要上Dijkstra邻接表几乎是最优选择因为堆优化版本里最频繁的操作是“遍历某个节点的所有邻居”表结构天然适合。2.3 建图代码十分钟敲熟邻接矩阵建无向图的标准写法int[][] graph new int[n][n]; for (int i 0; i n; i) { Arrays.fill(graph[i], INF); graph[i][i] 0; } for (int i 0; i m; i) { int u in.nextInt(); int v in.nextInt(); int w in.nextInt(); graph[u][v] Math.min(graph[u][v], w); graph[v][u] Math.min(graph[v][u], w); }注意两点一是无向图要双向赋值很多新手只写了一条边结果后面对不上二是如果有重边用Math.min取最小权值不然可能被后读入的较大边覆盖。邻接表建图就更常见了Listint[][] graph new List[n]; for (int i 0; i n; i) { graph[i] new ArrayList(); } for (int i 0; i m; i) { int u in.nextInt(); int v in.nextInt(); int w in.nextInt(); graph[u].add(new int[]{v, w}); graph[v].add(new int[]{u, w}); }如果你遇到的是无权图每条边没有长度可以简化成ListInteger[]每个元素直接存邻居编号。这两种建法练熟了以后基本所有图题都能直接套。还有一个小提醒邻接表如果明确知道边数很多可以提前给每个ArrayList设置初始容量比如new ArrayList(degree)减少扩容次数。不过机试数据规模一般没必要这么抠知道有这回事就行。3. 遍历是图论地基DFS与BFS模板还有三个高频炸点3.1 DFS模板与递归风险DFS适合解决“从某个点出发能走到哪些点”“连通块计数”这类问题。最标准的递归模板boolean[] visited new boolean[n]; void dfs(int u) { visited[u] true; for (int[] edge : graph[u]) { int v edge[0]; if (!visited[v]) { dfs(v); } } }然后从某个起点调用一次就能把整个连通分量扫完。如果想要统计连通块数量遍历所有节点遇到没访问过的就DFS一次并计数。递归写法有个隐藏风险如果图是一条很长的链比如说N20000的城市一字排开递归深度可能把栈压爆。Java默认栈大小有限深度到几千上万层时可能抛StackOverflowError。遇到这种数据特征改成显式栈DequeInteger stack new ArrayDeque(); stack.push(start); while (!stack.isEmpty()) { int u stack.pop(); if (visited[u]) continue; visited[u] true; for (int[] edge : graph[u]) { int v edge[0]; if (!visited[v]) { stack.push(v); } } }注意用栈模拟DFS时节点可能被多次push所以出栈时要靠visited判断是否已经处理过。这也是两种写法之间最容易搞混的地方。3.2 BFS模板入队时标记是铁律BFS解决的是“最短步数”“分层遍历”。模板比DFS更固定int[] dist new int[n]; Arrays.fill(dist, -1); DequeInteger queue new ArrayDeque(); dist[start] 0; queue.offer(start); while (!queue.isEmpty()) { int u queue.poll(); for (int[] edge : graph[u]) { int v edge[0]; if (dist[v] -1) { dist[v] dist[u] 1; queue.offer(v); } } }我见过最多的问题就是标记时机。有些人习惯先入队、等出队再标记这在普通BFS里会出大问题同一个节点可能被多个邻居分别加入队列队列里面出现大量重复节点。在复杂图里重复次数一多轻则超时重则逻辑错乱。所以请记住普通BFS必须在入队那一刻就标记用dist[v] -1做判断本身就完成了标记。出队时不需要再管它反正不会第二次进来。3.3 三个高频炸点第一个炸点是“图不连通”。题目如果只从一个起点出发做遍历那无所谓但连通块统计、多起点可达性问题必须用一个for循环把所有节点都扫一遍否则漏掉一部分节点。这个错误非常隐蔽因为样例数据常常恰好都是连通的你测样例能过一提交就暴露。第二个炸点是“节点编号从1开始”。机试描述经常是“N个城市编号1到N”如果你数组只开n个长度读入时直接用graph[u]分分钟下标越界。解决办法很简单数组开成n 1遍历范围从1到n。这种错在紧张时特别容易犯我建议准备阶段就把它当成条件反射。第三个炸点是“迷宫题的图不是邻接表”。当题目给的是一个二维矩阵比如grid[i][j]表示格子让你求从左上到右下的最少步数很多人还在想怎么建邻接表其实网格本身就是图。你把每个格子当作节点上下左右四个方向就是四条边方向数组解决int[] dx {-1, 1, 0, 0}; int[] dy {0, 0, -1, 1};BFS的时候用新坐标nx x dx[k]、ny y dy[k]注意边界判断和已访问标记。这类题数据规模一般比较大但BFS的时间复杂度是O(行数×列数)只要标记写对一定能在时限内跑完。4. 最短路径两件套Dijkstra与Floyd的适用边界4.1 堆优化Dijkstra模板带权图的最短路径机试里十有八九是正权边Dijkstra就是标准答案。很多教材先教朴素版O(n²)但机试更建议直接背堆优化版因为复杂度和代码量都在可控范围。int[] dist new int[n]; Arrays.fill(dist, INF); dist[start] 0; PriorityQueueint[] pq new PriorityQueue((a, b) - a[1] - b[1]); pq.offer(new int[]{start, 0}); while (!pq.isEmpty()) { int[] cur pq.poll(); int u cur[0]; int d cur[1]; if (d dist[u]) continue; // 过期的节点跳过 for (int[] edge : graph[u]) { int v edge[0]; int w edge[1]; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.offer(new int[]{v, dist[v]}); } } }这里有两个新手最容易踩的点。一是PriorityQueue的排序规则(a, b) - a[1] - b[1]会让距离小的先出队这是堆优化最关键的一步。二是if (d dist[u]) continue这行很多人觉得可有可无实际上它能把堆里已经失效的节点快速跳过省下大量无效运算。数据规模一大没有这一行的版本可能要跑一秒有这一行能压到几十毫秒。无穷大INF的设置也有讲究。别用Integer.MAX_VALUE否则dist[u] w可能直接溢出变成负数导致判断乱套。我习惯用1_000_000_000既够大两个相加也不会超过int范围安全好用。4.2 Floyd小数据量下的无脑解法Floyd是“任意两点最短路径”的暴力美学。三重循环解决所有问题代码短到几乎没有操作空间long[][] dist new long[n][n]; for (int i 0; i n; i) { Arrays.fill(dist[i], INF); dist[i][i] 0; } // 读边dist[u][v] min(dist[u][v], w) for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } }关于Floyd最容易被问到的就是“为什么k循环要放最外层”。我打个比方k表示“允许经过的中间节点的范围”一开始一个中间节点都不允许然后逐步放开允许经过节点0、节点1……直到全部放开。这个动态规划的递推顺序要求k必须先从外层推进如果k放内层中间节点范围就乱套了算出来的距离会是错的。Floyd的适用前提是n足够小。n200时三重循环800万次稳稳的n500时1.25亿次Java可能卡在时限边缘n1000就别想了。所以Floyd只在“数据点少但要求任意两点距离”时用。4.3 怎么选最短路径算法我自己做选择的时候会先回答三个问题问题是不是“从一个固定起点出发”是用Dijkstra。点数是不是很小而且多个点之间都要算距离是用Floyd。边有没有权值如果每条边等价比如迷宫就是每步代价1那根本不用上DijkstraBFS就是最快的最短路算法。这里补充一个很多人忽略的点无权图求最短步数BFS时间复杂度O(nm)比堆优化Dijkstra的O((nm)log n)快一个级别。所以不要一看到“最短”两个字就上Dijkstra先看边权是不是都一样。题目特征首选算法单源固定起点 正权边Dijkstra堆优化任意两点最短 n≤300Floyd每条边花费相等BFS存在负权边Bellman-Ford机试基本不考5. 拓扑排序与并查集两类高频图变形的快速识别5.1 Kahn拓扑排序模板“任务依赖”“课程排序”“编译顺序”这类题核心就是拓扑排序。我用的一直是Kahn算法思路清晰不断找入度为0的节点删掉它以及它的出边重复直到所有节点处理完。int[] indegree new int[n]; for (int u 0; u n; u) { for (int v : graph[u]) { indegree[v]; } } DequeInteger queue new ArrayDeque(); for (int i 0; i n; i) { if (indegree[i] 0) { queue.offer(i); } } ListInteger order new ArrayList(); while (!queue.isEmpty()) { int u queue.poll(); order.add(u); for (int v : graph[u]) { indegree[v]--; if (indegree[v] 0) { queue.offer(v); } } } if (order.size() n) { // 说明图里有环无法完成拓扑排序 }判断有环的写法就在最后一行能排出来的节点数少于总节点数说明有环。这个判断在“判断课程能否全部修完”这类题里是必答的。另外有个常见变形如果题目要求输出“字典序最小”的拓扑序列把普通队列换成优先队列按节点编号排序即可其余代码不动。5.2 并查集无向图连通性的短武器并查集不算严格的图遍历但它在处理“连通性”问题时比DFS/BFS更短更爽。典型题是“省份数量”“朋友圈”“判断两点是否连通”“冗余连接”。模板我几乎是背下来的int[] parent new int[n]; int[] rank new int[n]; for (int i 0; i n; i) { parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void union(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return; if (rank[rx] rank[ry]) { parent[rx] ry; } else { parent[ry] rx; if (rank[rx] rank[ry]) { rank[rx]; } } }这里的find用了路径压缩union用了按秩合并两个优化合起来能让树的高度保持很低。我自己的经验是就算不写按秩合并只写路径压缩在机试数据下也基本够用但按秩合并代码也就多三行写上更稳。统计连通块数量时初始值设为n每次union合并成功就减一最后剩下的数字就是连通块个数。这个技巧比遍历所有节点一遍更快而且代码几乎零成本。5.3 让“隐形图”现形变形题的识别套路有些题一眼看不出是图但本质就是图。把这些套路记熟了考试时少走很多弯路。迷宫、岛屿、二维矩阵里的路径问题本质是“网格图”用方向数组配合BFS/DFS。“单词接龙”“开锁密码”“状态最少步数”这类题每个状态是一个节点每次变换是一条边目标是最短步数那就是无权图BFS。“判断是否存在一个合法序列完成所有依赖”是拓扑排序“两个元素是否在同一个集合里”是并查集“社交网络里有多少个独立圈子”可以并查集也可以DFS。我原来说过一句话机试里的图题难度不在算法本身而在你能不能看穿那层文字包装。模板就那么多识别能力才是拉开差距的地方。6. 真题流程复盘从读题到AC的执行策略6.1 拿到一道图题后的操作顺序我参加过的机试和给朋友模拟考的经历反复验证了一套流程基本可以应对90%的图题。第一步读题时划关键词把“节点”“边”“问题目标”先摘出来。比如“N个城市M条道路每条道路通行时间求从1到N的最少时间”这里节点是城市边是道路目标是单源最短路径。第二步看数据范围。这一步决定后续所有选型N只有200Floyd随便写N是10000必须邻接表DijkstraN是100000DFS都要小心递归深度优先用栈写法或BFS。第三步先写输入解析再写核心算法。我见过太多人算法思路清晰但输入解析写错最后全部白费。尤其是无向图要双向加边、编号从1开始要开n1这类细节写完输入之后先自己口算一遍小样例确认图建对了再往下写。第四步处理边界。比如空的图只有一个节点、起点终点就是同一个点、存在孤立节点、存在重边。这些情况不会出现在正常样例里但会出现在测试数据里。写完之后自己构造两三个非标准测试用例跑一遍比盯着代码干看有效得多。6.2 自检清单我把容易踩的坑列成一张自检表提交前快速过一遍检查项具体要点数组大小编号从1开始必须开n1无向图双向加边是否对u和v都执行了addvisited/dist标记时机BFS是否在入队时标记INF取值避免Integer.MAX_VALUE相加溢出Dijkstra跳过过期节点是否写了if (d dist[u]) continueFloyd的k层是否在最外层拓扑排序的环判断order.size() n并查集find压缩是否写了路径压缩多组测试用例静态数据是否重置连visited都没有这张表不是背的是拿来用的。每写完一题边提交边过一遍养成习惯后能挡住大部分低级错误。6.3 考前一周怎么冲刺如果离机试只剩一周图的部分应该怎么准备我的建议是抓大放小。四个模板必须背到闭眼能默写BFS、堆优化Dijkstra、Kahn拓扑排序、并查集。DFS递归版要会写非递归版至少看一遍。然后挑五道高频题练手迷宫最短步数、单源最短路、任务依赖是否成环、省份连通数量、判断两点是否连通。这五道题覆盖了图论板块的核心套路。练习方式上我个人的体会是“每天上手敲一遍模板比看十篇题解有用”。机试是写代码的考试不是看代码的考试。看的时候觉得都懂一上手才发现各种细节问题。时间再紧张每天两遍模板的时间一定要留出来。考场上如果遇到图题卡住了先把输入读完、把图画出来。很多时候你觉得没思路是因为脑中的图还没成型。哪怕只画了一个小样例的草图遍历该从哪开始、边该往哪走一下子就清楚了。图题在机试里反而是拿分最稳的题前提是你真的在考前把它当回事。我自己当年就是吃了“觉得图难、拖到最后”的亏。后来重新总结才明白机试里的图论考来考去就是遍历、最短路、拓扑、连通性这几个固定套路模板熟练之后做起来比字符串处理还顺手。你把这篇文章里的模板吃透再按第六部分的流程练上几道题图这个专题就不再是短板了。