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

关于生成树的说法，错误的是（ ）。

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

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

【考点】生成树存在性｜生成树边数｜树的结构特性

🧠 解题思维

生成树定义核心：连通、n 个顶点、恰好 n-1 条边、无环。

• A 项：连通图一定存在生成树，这是定理，任何连通图都能通过逐步删边破环保持连通
• B 项：生成树若存在必为树结构 → n-1 条边；若图不连通则无生成树，逻辑完备
• C 项：n 顶点 n-1 边若无环必为树，树只有唯一生成树（自身）；若有环则必不连通 → 无生成树
• D 项：这是命题人挖的最深坑！"n 顶点 n-1 边"的图可能是森林（含多个连通分量），森林没有生成树