克鲁斯卡尔算法：最小生成树构建与实现

在17052317班的於文卓同学提交的数据结构实践课报告中，主题是"最小生成树问题"，该报告是针对一个实际问题进行研究的，即在n个城市之间以最低成本建立通信网络。问题的关键是要找到一个仅包含n-1条边的树形结构，使得所有城市都能互相连接，且总费用最小。这个问题通常通过经典的算法，如克鲁斯卡尔算法来解决。 报告要求学生实现以下任务： 1. **克鲁斯卡尔算法**：这是核心任务之一，用于找到一个图的最小生成树。克鲁斯卡尔算法基于贪心策略，每次选择当前未被选中的边中权值最小的一条，加入到已选集合中，直到所有城市都连通。这个过程确保了最终生成的树是最优的。 2. **MFSet抽象数据类型**：最小生成树问题常常涉及并查集数据结构，用于表示各个城市的归属关系。MFSet（Minimum Find Set）数据结构可以有效地支持并查集操作，如查找（find）、合并（union）等，以跟踪每个城市所属的最小生成树。 3. **输出边及权值**：报告要求输出最小生成树中每条边的起始点和终点，以及它们的权值，以便于理解和评估算法的结果。 报告提供了测试数据，展示了包含8个城市的例子，以及对应的边的权值。程序采用了C++语言编写，包括主程序、图的存储模块（定义结构体`Node`表示边的信息，如起点、终点和权值）和操作单元模块（实现并查集功能）。代码中使用了`map`数据结构方便地根据字符查找数据，并注意处理用户输入时的多余回车。 算法分析部分强调了并查集的思想应用，以及对C++标准库函数的利用。整个程序的架构清晰，包含了用户手册和源代码，展示了良好的编程规范。在附件中，作者注明了作者信息、修改日期，以及一个示例输入数据和对应的节点结构。 这份报告详细阐述了最小生成树问题的解决方案，包括理论背景、实现步骤、数据结构选择和关键算法的运用，具有较高的实践价值和学习意义。