GESP 八级 · GESP 202412 C++ 八级 第 4 题

使用邻接表表达一个简单有向图，图中包含 $v$ 个顶点、$e$ 条边，则该出边表中边节点的个数为（ ）。

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

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

【考点】图存储结构｜有向图邻接表

考纲定位： GESP 八级数据结构模块，考查“图”的存储方式，重点区分有向图邻接表与无向图邻接表的存储差异。命题人卡住的是“有向边在邻接表中只存一次”这一易混点，多数考生会混淆有向与无向图的存储节点数。该题测试学生对邻接表基本结构的理解，是图算法的基础。命题人通过此题检验考生对图存储结构的掌握程度，尤其是区分有向与无向图的存储节点数。这是 GESP 八级数据结构的典型考点。

解题思维： 看到“有向图”和“邻接表”，立刻想到每条有向边在出边表中只出现一次；出边表里存的是边节点，所以总数就是边数 e。选项 A（v×(v−1)）是简单有向图的最大边数，但题干并未限定图是完整的；选项 B（v×v）还包含了自环；选项 C（2×e）是无向图邻接表的边节点总数（每条边存两次）。因此正确答案是 D。邻接表的核心是“出边表”，每个顶点维护一个链表，链表中的每个节点代表一条有向边。因此，所有出边表中的边节点总数必然等于有向边的总数 e。

陷阱拆解： A 项是“完全有向图”的边数，但题干没说图是完整的；B 项还包含了自环；C 项是无向图邻接表的边节点总数（每条边存两次）。最阴险的细节是“出边表中边节点的个数”——它不是图里边的条数，而是存储结构里占用的节点数。只背结论会掉进 C 项陷阱。简单有向图不含自环，所以 e 条边对应 e 个边节点。

反命题思维： 若改成“无向图”，答案就是 C；若问“邻接表中所有节点的个数”，答案是 v+e。刷到这类题先问自己：“命题人想考图还是考存储？”