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

一个图中，每个结点表达一个人，连接两个结点的边表达两个结点对应的人相互认识，则这个图可以用来表达社交网络。

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

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

【考点】图的定义｜图论建模｜社交网络抽象

🎯 考纲定位：GESP 七级 图论基础模块（数据结构与算法）。命题人卡住的是考生对"图的定义"的模糊认知——很多人以为图必须有向、必须连通，其实无向连通图才是社交网络的标准建模方式。

🧠 解题思维：先识别"结点=人、边=互相认识"是图论中对关系的抽象，属于图的基本定义范畴。再看"社交网络"的建模本质就是节点代表个体、边代表关系，这与题目描述完全一致。通法：任何"用图表示某类对象及其关系"的问题，第一步先确认对象对应结点、关系对应边，第二步看是否允许自环/重边/方向——社交网络默认无向、可自环、可重边，题目未限制，故可直接判定正确

🪤 陷阱拆解：选项 B 的"错误"来源是对"图"的刻板印象。命题人故意用"社交网络"这个生活化概念，诱导考生过度联想"必须有向""必须连通""不能自环"等额外约束。其实题目只定义了结点和边的对应关系，未加任何限制，按定义完全成立。阴险细节："表达"一词看似中性，实则隐含"能否表示"的判定逻辑——考生若只背结论"社交网络=图"，就会忽略"结点、边"的具体映射过程，直接选错。

🔄 反命题思维：若把"互相认识"改成"单向关注"，图就要加方向，答案变错；若把"结点"改成"群聊"，边就要代表群成员关系，建模方式完全不同。这类题本质是考"图论建模的适用性"，而非具体计算。刷到"图表示某系统"类题，先问"系统里有什么实体？关系方向如何？"再对照图定义，别被生活场景带偏。