数据 结构 实验 三 生 成 最 小 树

数据结构实验3 ：图的遍历生成树

实验内容及原理

1. 通过键盘输入n个顶点与m条边（6<=n<=16，n-1<=m<=20）及其对应的权重值，构建图的邻接矩阵与邻接表两种存储方式，并将所生成的邻接矩阵和邻接表进行输出。
2. 利用Prim算法计算该图的最小生成树。具体包括函数 void Prim(AMGraph G, VerTexType u) 和用于输出边集数组的函数 void PrintEdge(Edgeset Sedge, int n)。
3. 编写测试程序（即主函数），通过调用上述相关函数，首先构建并输出一个无向带权图，随后生成其最小生成树并完成边集的输出。

分析

本次实验所涉及的内容相对基础，主要涵盖图的存储方式、遍历方法以及生成最小生成树的相关算法。其中，图的存储需采用两种不同的实现方式，即邻接矩阵与邻接表。
Prim算法的核心思想在于维护两个集合：一个集合用于存储当前已纳入的节点V{}，另一个集合则包含与V{}中节点直接相连的所有边E{}。在每一步操作中，从E{}中选取一条终点未被包含在V{}内且长度最短的边，并将其加入到V{}中，同时对E{}进行更新。这一过程持续进行，直到所有节点都被纳入V{}之中。为了从E{}中高效地获取最短边，在初级实现阶段可以采用数组结合遍历的方式；而在更高级的实现方案中，则可引入优先队列