树的最大连通分支问题 说明书.doc

数学与计算机学院 课程设计说明书 课 程 名 称: 算法设计与分析-课程设计 课 程 代 码: 7106620 题 目: 树的最大连通分支问题 年级/专业/班: 2008/信息与计算科学 /2班 学 生 姓 名: 何德宏 学　　 号: 312008070102221 开 始 时 间: 2011 年 12 月 5 日 完 成 时 间: 2011 年 12 月 18 日 课程设计成绩： 学习态度及平时成绩（30） 技术水平与实际能力（20） 创新（5） 说明书撰写质量（45） 总 分（100） 指导教师签名： 年 月 日 目 录 1 引 言 1 1.1 问题的提出 1 1.2任务与分析 1 2 程序的主要功能 3 2.1树的存储功能 3 2.2连通分支的计算功能 3 3 程序运行平台 3 4 总体设计 3 4.1算法设计 3 4.2流程设计 6 5 模块分析 7 5.1 树的存储模块 7 5.2 计算树的最大连通分支模块 9 6 系统测试 10 7 结论 14 8 致谢 15 9 参考文献 16 附录 17 摘 要 随着计算机的普及，人们解决问题的方法也变得多样化，同一个问题总想用简单实用的方法去解决，其中树的最大连通分支问题就是一个很典型的例子，我们可以用蛮力法和动态规划法去实现，但用动态规划的方法效率更高。因此该系统利用动态规划的方法编程实现了求解树的最大连通分支问题，该程序能够快速输入树的结构，并能计算出树的最大连通分支。此外，代码简洁易懂，界面友好，能一目了然的看出最终的结果，便于操作。 关键词：树的最大连通分支;动态规划; …… 1 引 言 1.1 问题的提出 连通分支定义： 设X是一个拓扑空间．对于X中的点的连通关系而言的每一个等价类称为拓扑空间X的一个连通分支．如果Y是拓扑空间X的一个子集．Y作为X的子空间的每一个连通分支称为X的子集Y的一个连通分支． 拓扑空间X≠ 的每一个连通分支都不是空集；X的不同的连通分支无交；以及X的所有连通分支之并便是X本身．此外，x，yX属于X的同一个连通分支当且仅当x和y连通．给定一棵树T，树中每个顶点u都有一个权w(u)，权可以是负数。现在要找到树T的一个连通子图使该子图的权之和最大）不包含根（f[x,0]）:f[x,0]=max{max(f[son[x],1],f[son[x],0])}。:　　　　　 最大连通分支在子树或树中，因此对树进行遍历，依次求出以每个结点为树根的最大连通分支权值 该问题具有两个子性质： 最有子结构性质 子问题重叠性质 算法实现： 1、对于叶子结点或儿子个数为0的结点，其最大连通分支权值为该 结点的权值 2、某一结点的最大连通权值＞0，则将其值加到它的父亲结点的最大连通权值，反之舍弃该值 最后求出根结点的最大连通权值，结束遍历 所求最大连通分支权值即结点 的最大连通权值 最后采用动态规划求解，类似于图的后续遍历，这方法避免了很多蛮力法的缺点，因此效率也得到了很大的提高。 2 程序的主要功能 2.1树的存储功能 要想计算树的最大连通分支，首先需要给定一棵树，因此需要存储树的基本信息，其中最重要的就是节点信息，用结构体来表示：包括结点的权值（weight），结点的父亲结点（father），结点的儿子结点（child），结点的最大连通分支权值（wmax）和结点是否被访问过（visited），最后需要用数组（动态创建）表示树。 2.2连通分支的计算功能 树创建完后，首先要对树结构进行初始化，并需要输入数据建立树结构，然后确定一个树根，对每一个结点用动态规划的方法进行遍历，找出最大连通分支并计算出权值，最后输出最大的连通分支和其权值。 3 程序运行平台 WINDOWS XP/WIN 7 VC++6.0。 具体操作如下：进入Visual C++6.0开发环境,在开发环境的主窗口中选择File|New菜单项，在弹出的对话框中单击Project选项卡，选择C++ Source File，命名为“树的最大连通分支问题”，再制定保存路径，单击OK键完成新建。再在编辑窗口中编辑代码，编译，链接，，进行调试，执行，然后输出结果。 4 总体设计 4.1算法设计 1、数据结构 struct Cnode //用结构体来表示结点 { long weight; //结点的权值 int father; //结点的父亲结点 int childnum; /