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

一个包含 $ V $ 个顶点的连通无向图，其任何一棵生成树都恰好包含 $ V - 1 $ 条边。

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

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

【考点】图论基础｜生成树性质｜连通图判定

1. 🎯 考纲定位

GESP 七级"图论算法"模块，考查生成树的核心特性。命题人卡住的是考生对树结构本质的模糊——很多人背过"生成树有 V-1 条边"，但只当记忆口诀，没理解这其实是连通无环图的结构约束。