1、下面关于树和图的说法，不正确的是({{ select(1) }}）。

• 树有一个根节点，图没有根节点
• 树没有环，图可能有环
• 树有明确的层次和父子关系
• 节点数相同的树，边数少于图

2、 生成树

希希是城市规划设计师，要将下图中的 6 个地点用路连起来（一条路只能连接两个地点），使每个地点都能到达任何其他地点。最少要修（ {{ input(2) }} ）条路。

3、并查集

森林国有 15 个城市，国王想在城市间修建铁路。因为地形和气候原因，修建每条铁路的花费有高有低。 设计师向国王提供了规划图，图中每棵树代表一个城市，城市间有灰线连接，表示两个城市间可以修建铁路，费用在旁边标出。如下图所示：国王希望新修建的铁路能使任何两个城市互通，又不想花太高的代价。

如果只选择部分路段修建铁路，最小总花费是（ {{ input(3) }} ）

4、 并查集的路径压缩

恐龙乐园的规划图中有 n 个小岛，m 座小桥，每座桥连接两个小岛。下图是 n=5，m=8 的一个例子：

希希发现，如果拆除一些桥，仍然能使任何两个小岛都可以互通。最多可以拆除（{{ select(4) }} ）座桥。

• n - m
• m - n
• m - m - 1
• m - n + 1

5、 Kruskal 算法

4 间教室各有 1 台电脑，学校要用网线将 4 台电脑连接起来，组成网络。下图每两台电脑之间，虚线旁边标的数表示连接两台电脑所需网线的长度（与虚线的实际长度无关），要使所有电脑都在网络中，最少需要网线的长度是（ {{ input(5) }} ）。

注意：只要电脑有一条线与网络连通即可，不考虑其他网络设备对网线的消耗。

6、Prim 算法

已知无向图如下，它的最小生成树上各权值的累加和为（ {{ input(6) }} ）。