GESP 七级 · GESP 202506 C++ 七级 第 25 题

如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道级导航需求。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】简单图｜多值图

考纲定位 命题人把“简单图”直接塞进七级卷，就是要卡住只会背定义的考生。GESP 七级 C++ 真题考的是“图模型是否支持值的存储”，而不是“连通性”。简单图的核心就是“无重复边”，但车道级导航需要知道某条路有几条车道，简单图无法区分（比如城市 A 到 B 有两条车道，简单图只能画一条边）。这类题通法是：先明确题干中的图模型是否支持“值”的存储，再对照需求判断。

解题思维 看到“简单图”和“车道级导航”要立刻反应：简单图只记录连不连，不记录车道数。车道级需要知道某条路有几条车道，简单图无法区分（比如城市 A 到 B 有两条车道，简单图只能画一条边）。这类题通法是：先明确题干中的图模型是否支持“值”的存储，再对照需求判断。

陷阱拆解 命题人太狡猾了，用“简单图”这个词直接卡住只会背定义的考生。简单图的核心是“无重复边”，但题目要求“车道级”——这意味着同两个城市之间可能有多条车道，需要多条边。如果你只记得“简单图没有重边”，却没意识到车道数可以映射为边数，就会误以为简单图够用。正确思路是：车道数=边数，所以必须用“允许重边的图”（即多值图）。

反命题思维 假如改成“城市级导航”，答案直接变 A，因为简单图就能表示连通性；改成“多值图”也能选 A，因为多值图允许重边，车道数就是边数。命题人想考的是“图模型是否支持值的存储”，而不是“连通性”。

我是 ， 打造的模型。