算法分析与设计实验

《算法分析与设计实验》由会员分享，可在线阅读，更多相关《算法分析与设计实验（15页珍藏版）》请在金锄头文库上搜索。

1、算法分析与设计实验算法分析与设计实验电子科技大学计算机学院电子科技大学计算机学院实验时间：实验时间：十一周上午十一周上午:3011:30十二周十二周 上午上午:3011:30十三周十三周 上午上午:3011:30十四周十四周 上午上午:3011:30实验安排实验安排 实验老师：实验老师：官老师 上机地点：上机地点：科研二号楼504实验内容实验内容实验名称实验名称： Kruskal算法的编程实现算法的编程实现 实验目的实验目的：加深对算法原理及实现过程的理解加深对算法原理及实现过程的理解 实验原理实验原理 使用使用Kruskal算法可以构造一棵最小生算法可以构造一棵最小生成树成树实验内容实验内容

2、 实验内容实验内容： 理解理解Kruskal算法的原理，编程实现算法的原理，编程实现KruskalKruskal算法算法, ,进行如下几个方面的设计进行如下几个方面的设计与实现：与实现：实验内容实验内容 1 1、无向图的表示与存储。由于该算法、无向图的表示与存储。由于该算法的输入应为一个带权无向图，所以需要的输入应为一个带权无向图，所以需要对该输入进行合理的表示。另外，应提对该输入进行合理的表示。另外，应提供方便的接口，使得用户可以容易地进供方便的接口，使得用户可以容易地进行输入数据的更改（如使用文件来存储行输入数据的更改（如使用文件来存储无向图数据）。无向图数据）。2 2、堆排序算法。由于、

3、堆排序算法。由于KruskalKruskal算法涉及堆算法涉及堆排序，所以要首先对后者进行完整的实排序，所以要首先对后者进行完整的实现。现。3 3、面向对象的程序表达。虽然不使用面面向对象的程序表达。虽然不使用面向对象的方法也能实现该算法，但考虑向对象的方法也能实现该算法，但考虑到面向对象能更好地进行图的表示，还到面向对象能更好地进行图的表示，还是建议使用其进行算法的具体实现。是建议使用其进行算法的具体实现。 、算法实际运行时间与实际消耗空间算法实际运行时间与实际消耗空间的统计。其中，运行时间考虑使用不的统计。其中，运行时间考虑使用不同的尺度，包括比较次数、运行秒数同的尺度，包括比较次数、运行

4、秒数等。特别是比较次数对于理解算法的等。特别是比较次数对于理解算法的复杂度有着更好的效果。复杂度有着更好的效果。、图形化的显示。本内容属于扩展要求。图形化的显示。本内容属于扩展要求。如果能使用如果能使用JavaJava或或VCVC里的图形模块进行结里的图形模块进行结果的显示无疑是非常有意义的。果的显示无疑是非常有意义的。 考察不同的输入数据、输入规模对时间、考察不同的输入数据、输入规模对时间、空间消耗的影响。本实验中，不同的输入空间消耗的影响。本实验中，不同的输入数据对时间、空间的消耗不会有太大波动。数据对时间、空间的消耗不会有太大波动。而不同输入规模会有很大影响。而不同输入规模会有很大影响。

5、 实验要求实验要求 实验前要做好充分准备，包括程序清实验前要做好充分准备，包括程序清单、调试步骤、调试方法。单、调试步骤、调试方法。 实验后要进行对程序结果的详细分析实验后要进行对程序结果的详细分析 等。等。实验报告实验报告 1 1、程序说明。说明程序的功能、结构。、程序说明。说明程序的功能、结构。 2 2、调试说明。包括上机调试的情况、上、调试说明。包括上机调试的情况、上机调试步骤、调试所遇到的问题是如何解机调试步骤、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，决的，并对调试过程中的问题进行分析，对执行结果进行分析。对执行结果进行分析。 3 3、写出源程序清单和执行结果。、写

6、出源程序清单和执行结果。 实验思考实验思考 如何实现如何实现PrimPrim算法，其实现与算法，其实现与KruskalKruskal算法有哪些相同点，哪些不同点算法有哪些相同点，哪些不同点 实验报告要求实验报告要求1、实验报告的格式必须打印2、实验报告的内容必须手写，否则拒收！ 实验报告里面内容每一项都必须填写。3、报告中要有实验结果的截图 4、每次实验报告后面须附源程序清单(作为附件)，源 程序必须要有注释、可以打印。5、所有实验完成后，将实验报告按顺序装订并用学校 统一规定的封面贴好、按封面的尺寸裁剪整齐。 在指定的时间交到指定的地点。实验成绩的算法实验成绩的算法一、成绩按百分制计二、考勤占 30分分三、实验结果占 30分分四、实验报告占 40分分注：不交实验报告者按零分计注：不交实验报告者按零分计n实验课件、报告样表实验课件、报告样表