试题出自试卷《南京邮电大学2005年811数据结构真题解析》

答：
（1）生成的最小代价生成树如下所示：

（2）当生成树上有5条边时的并查集的状态：{1、2、4、5、6、7}、{3}。

【考点】本题考查数据结构--图--最小代价生成树--构造最小生成树--Kruskal算法--Kruskal算法构造最小生成树。
【解析】
（1）克鲁斯卡尔（Kruskal）构造最小生成树算法的描述：先构造一个只含 n 个顶点、边集为空的子图，把子图中各个顶点看成各棵树上的根结点。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依此类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。

（2）在 Kruskal 算法中，需要使用并查集来维护图的连通性。并查集是一种常用的数据结构，用于维护元素的集合。并查集中每个元素都有一个代表元素，它代表着所在的集合。并查集包含两个主要的操作：查找和合并。查找操作用于查找元素所在的集合，而合并操作用于将两个集合合并成一个集合。