"山大计科17.3数据结构与算法实验报告：贪婪算法求最小生成树"

本实验报告是张愈博同学在山东大学计算机科学与技术学院数据结构与算法课程的实验报告，实验题目为贪婪算法实验，学时为4学时，实验日期为2018年12月22日。实验目的是要求掌握最小生成树的Prim算法和Kruskal算法及其实现。在软件环境上，使用的是Windows 10系统和Dev C 5.11开发环境。 实验内容包括创建加权无向图类，其中图没有重边和自环，存储结构分别使用邻接矩阵或邻接链表，并提供必要的基本操作。另外，还需要键盘输入图中顶点的个数n和边的数目e，以三元组(i,j,w)形式依次输入图的每一条边或随机生成含e条边的图，其中(i,j,w)表示顶点i和顶点j之间拥有权值为w的边，建立图。最后，对建立好的图，分别使用Prim算法和Kruskal算法求最小生成树，输出求得的最小生成树（以文本形式输出生成树中的各条边及对应的权值）。 在整体思路上，本题使用的加权无向图在实验12中已经写好，存储结构选择邻接矩阵。因此，需要关注的是Prim算法和Kruskal算法。Prim算法是一种贪心算法，其基本思想是以一个顶点为起始生成树，然后逐步将不在生成树中且权值最小的边加入生成树，直到所有顶点都在生成树中为止。而Kruskal算法是另一种贪心算法，其基本思想是将图中的所有边按权值从小到大排序，然后依次加入到生成树中，如果形成了环，则舍弃，直到生成树中有n-1条边为止。 对于Prim算法的具体实现，可以使用堆或优先队列来高效地选择权值最小的边，从而构建最小生成树。而Kruskal算法的具体实现，则需要使用并查集来判断加入的边是否会构成环。 在实验中，需要考虑的数据结构包括加权无向图的存储结构，比如邻接矩阵；算法上，则需要考虑Prim算法和Kruskal算法的具体实现细节，以及堆、队列和并查集等数据结构的使用。 总的来说，本实验报告以贪婪算法为主题，通过对最小生成树的Prim算法和Kruskal算法的实现，旨在让学生掌握贪心算法的具体实现细节，并通过这个案例了解贪心算法的应用。通过实验，可以帮助学生加深对算法和数据结构的理解，提高解决问题的能力和编程实践技能。