最小生成树算法演示系统-MST

图论算法在交通网络规划、通信网络设计、电力系统布线等领域应用广泛。本项目旨在通过实现最小生成树的核心算法（Prim和Kruskal），构建一个交互式的算法演示系统。目标不仅在于展示算法原理，更重要的是建立理论与实际应用之间的桥梁，帮助学习者直观理解算法在资源优化配置中的价值，培养解决实际工程问题的能力。
包含六大核心功能模块：
1. 图结构管理模块：支持邻接矩阵表示的加权无向图，提供预置高速公路示例图和随机图
生成功能
2. Prim算法模块：实现基于贪心策略的最小生成树算法，时间复杂度O（V3），适合稠密图
3. Kruskal算法模块：实现基于并查集的算法，时间复杂度O（Elog E），适合稀疏图
4.算法对比分析模块：对比两种算法的执行过程、时间空间复杂度、适用场景
5. 高速公路应用场景模块：将抽象算法转化为具体的工程规划问题，提供成本效益分析
6. 交互式演示系统：提供7种操作的命令行菜单，支持用户交互和实时演示。
用户启动程序后，首先加载预置的高速公路网络示例图。通过交互式菜单，用户可选择：①查看图结构；②从指定城市开始执行
Prim算法并观察逐步构建过程；③执行
Kruskal算法并观察按权重排序的选择过程；④对比两种算法的结果和性能差异；⑤查看如何将最小生成树应用于高速公路建设规划；⑥创建新的随机测试图验证算法通用性；⑦查看算法正确性证明。整个流程形成"理论一实现一验证一应用"的完整学习

底层为数据结构层（邻接矩阵、边集合、并查集），中间层为算法核心层（Prim和Kruskal实现），上层为应用交互层（菜单系统和场景演示）。技术栈纯基于C
语言标准库，包括stdio.h用于输入输出，stdlib.h用于动态内存和随机数，stdbool.h用于布尔类型，limits.h用于无穷大定义。包含10个核心函数。
作为项目唯一开发者，我负责全部模块的设计与实现。具体成果包括：
1.实现两种算法的完整逻辑，代码覆盖率
100%，通过20+测试用例验证
2.设计并实现了并查集优化，使Kruskal算法在
1000条边规模下运行时间<0.1秒
3. 开发了交互式菜单系统，支持7种操作选项，用户输入错误处理完善度达95%
4. 构建了高速公路应用场景，将算法结果转化为具体的经济指标（投资成本、回收期）
5. 实现了随机图生成器，支持生成2-50个顶点、1-100%密度的测试图。
复杂度保证：代码严格遵循算法理论复杂度，Prim算法O（V2的平方）适用于邻接矩阵，Kruskal算法O（Elog E）通过并查集优化。
难点1:Kruskal算法中边的排序问题。最初使用快速排序，但在递归深度大时可能出现栈溢出。解决方案：改用优化的冒泡排序，并添加边数限制（MAX_EDGES=1000），确保在可控规模内稳定运行。
难点2：确保随机图连通性。随机生成的图可能不连通，导致最小生成树无法覆盖所有顶点。
解决方案：在随机图生成函数中，强制保证至少生成V-1条边，并在添加边时检查重复，使用邻接矩阵确保无向图对称性。