408 每日一题 Day7#

设一个含 $n$ 个结点的无向连通图采用邻接矩阵存储。若该图最小生成树唯一，则其邻接矩阵中值为 $0$ 的元素个数为（ ）。

A. $n^2-2(n-1)$
B. $n^2-(n-1)$
C. $(n-1)^2$
D. $\frac{n(n-1)}{2}$

正确答案：A#

解析：
对于含 $n$ 个结点的树，其边数为：$e=n-1$
由于无向图的最小生成树唯一，则无向图的边数等于最小生成树的边数
对于无向图，一条边对应邻接矩阵中的两个非零元素
因此非零元素个数为 $2e = 2(n - 1)$
则值为 $0$ 的元素个数是 $n^2 - 2(n - 1)$