图应用实战：克鲁斯卡尔算法与最小生成树构建

本篇文档主要介绍了数据结构课程设计中的一个实验——图的应用，特别是针对最小生成树问题的求解。实验的主要目的是帮助学生巩固图的基本概念，熟练掌握图的存储结构，并学会如何将这些理论知识应用于解决实际问题。 首先，实验的核心任务是使用克鲁斯卡尔(Kruskal's)算法来找到在n个城市间建立通信网络所需的最少边，形成最小生成树。问题背景设定为在n个城市之间建设通信网络，需要构建一个无向网，且边的权值是小于100的整数，这体现了实际场景对算法效率和精确度的要求。 在实现上，推荐使用边（带权）的数组表示图，而不是邻接矩阵或邻接表，因为这样更方便在查找权值最小的边时进行操作。图的结构体定义为`MGraph`，包含顶点数组`vexs`、邻接矩阵`arcs`，以及顶点数和边数的计数器`vexnum`和`arcnum`。邻接矩阵被定义为二维整数数组，用于存储顶点之间的连接关系。 实验数据部分给出了10个顶点之间的示例连接，如`ab6`、`ad5`等，权值代表了连接两点的成本。为了简化问题，这里的顶点数限定在30以内，且边的权值都是整数。 函数`LocateVex`的作用是查找某个顶点在图中的位置，通过遍历图结构来确定。`CreateGraph`函数用于创建图，传入`MGraph`类型的指针作为参数，表明函数会修改输入的图对象。 源代码部分展示了部分关键结构的定义和函数声明，例如顶点类型`Vertex`，最大名称长度`MAX_NAME`，最大顶点数`MAX_VERTEX_NUM`，以及邻接矩阵类型`AdjMatrix`。整个实验强调了将理论与实践相结合，让学生在解决实际问题的过程中深化对图数据结构的理解和应用能力。 总结来说，这个实验不仅锻炼了学生的编程技能，还通过实际案例让学员掌握如何运用图的存储结构和算法来优化网络构建成本，体现了数据结构在现实世界中的实用价值。