最小生成树课程设计

来源:百度知道 编辑:UC知道 时间:2024/05/13 00:54:38
1. 需求分析
以无歧义的陈述说明程序设计的任务,强调的是程序要做什么?明确规定:
(l)输入的形式和输入值的范围;
(2)输出的形式;
(3)程序所能达到的功能;
(4)测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。

2. 概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。

3. 详细设计
实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);画出函数的调用关系图。

4. 调试分析
内容包括:
(l)调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;
(2)算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想;
(3)经验和体会等。
5. 用户使用说明
说明如何使用编写的程序,详细列出每一步的操作步骤。

6. 测试结果
列出测试结果,包括输入和输出。这里的测试数据应该完整和严格,最好多于需求分析中所列。

7. 附录
带注释的源程序。如果提交源程序软盘,可以只列出程序文件名的清单。值得注意的是,报告的各种文档资料,如:上述中的前三部分要在程序开发的过程中逐渐充实形成,而不是最后补写(当然也可以最后用实验报告纸誊清或打印)。

给你说说思路吧

在所有的边中选择权值最小的一个边 对其进行如下操作:
将该边加入生成树中 如果存在环 则删除该边
重复上面的操作 n-1 次
即可找到包含n个结点的最小生成树

至于怎么判断是否存在环 可以使用并查集 当然 最简单的方法是为每个边建立一个bool型变量 其包含在生成树里面时 设置为true 否则为false 每次加边之前判断边的头结点和尾结点的bool变量是否都为true就可以

具体怎么实现 还是希望楼主自行CODE
毕竟这个是基本功