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

1、数学与计算机学院课程设计说明书课 程 名 称: 算法设计与分析-课程设计 课 程 代 码: 7106620 题 目: 树的最大连通分支问题 年级/专业/班: 2008/信息与计算科学 /2班 学 生 姓 名: 何德宏 学 号: 开 始 时 间: 2011 年 12 月 5 日完 成 时 间: 2011 年 12 月 18 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日目 录 1 引 言11.1 问题的提出11.2任务与分析12 程序的主要功能32.1树的存储功能32.2连通分支的计算功能33 程序运

2、行平台34 总体设计34.1算法设计34.2流程设计65 模块分析75.1 树的存储模块75.2 计算树的最大连通分支模块96 系统测试107 结论148 致谢159 参考文献16附录17 摘 要随着计算机的普及，人们解决问题的方法也变得多样化，同一个问题总想用简单实用的方法去解决，其中树的最大连通分支问题就是一个很典型的例子，我们可以用蛮力法和动态规划法去实现，但用动态规划的方法效率更高。因此该系统利用动态规划的方法编程实现了求解树的最大连通分支问题，该程序能够快速输入树的结构，并能计算出树的最大连通分支。此外，代码简洁易懂，界面友好，能一目了然的看出最终的结果，便于操作。关键词：树的最大连

3、通分支;动态规划; 1 引 言 1.1 问题的提出 连通分支定义： 设X是一个拓扑空间对于X中的点的连通关系而言的每一个等价类称为拓扑空间X的一个连通分支如果Y是拓扑空间X的一个子集Y作为X的子空间的每一个连通分支称为X的子集Y的一个连通分支 拓扑空间X 的每一个连通分支都不是空集；X的不同的连通分支无交；以及X的所有连通分支之并便是X本身此外，x，yX属于X的同一个连通分支当且仅当x和y连通树作为一种特殊的图，它本身就是连通的，里面还有许多的连通子图，当每个顶点加入权值后，可以计算出权值最大的连通子图。使用的方法可以有很多，其中蛮力法和动态规划是两种比较典型的方法，相对于蛮力法而言，动态规划

4、的方法效率更高，所以最后选择了动态规划方法来计算树的最大连通分支问题。1.2任务与分析给定一棵树T，树中每个顶点u都有一个权值w(u)，而且权值可以是正数或者负数。现在要找到树T的一个连通子图使该子图的权之和最大，要求编程实现计算出树的最大连通分支传统的方法为蛮力法，即依次以每一个顶点为根节点，然后找出以该节点为根节点的所有连通子图，分别计算出连通子图的权值之和，最后找出权值之和最大的连通子图，便可得出最后的结果，但该方法效率不高，如果给定是一棵有很多节点的树，那么这效率将会非常低下。为此，我们将使用动态规划的方法来求解此问题：对于以X为根的子树分两种情况考虑：（1）、包含根（fx,1）：fx

5、,1等于所有大于0的fsonx,1的和加wx。（2）、不包含根（fx,0）:fx,0=maxmax(fsonx,1,fsonx,0)。记忆话搜索递归求解。算法分析:最大连通分支在子树或树中，因此对树进行遍历，依次求出以每个结点为树根的最大连通分支权值树根rootT1T2W<0W>0Wr=Wr+Wt1rootT1T2W<0W>0树根rootT1T2 该问题具有两个子性质：最有子结构性质子问题重叠性质W>0W<0算法实现：1、对于叶子结点或儿子个数为0的结点，其最大连通分支权值为该 结点的权值2、某一结点的最大连通权值0，则将其值加到它的父亲结点的最大连通权值，

6、反之舍弃该值3、 最后求出根结点的最大连通权值，结束遍历4、 所求最大连通分支权值即结点 的最大连通权值最后采用动态规划求解，类似于图的后续遍历，这方法避免了很多蛮力法的缺点，因此效率也得到了很大的提高。2 程序的主要功能2.1树的存储功能要想计算树的最大连通分支，首先需要给定一棵树，因此需要存储树的基本信息，其中最重要的就是节点信息，用结构体来表示：包括结点的权值（weight），结点的父亲结点（father），结点的儿子结点（child），结点的最大连通分支权值（wmax）和结点是否被访问过（visited），最后需要用数组（动态创建）表示树。2.2连通分支的计算功能树创建完后，首先要对树

7、结构进行初始化，并需要输入数据建立树结构，然后确定一个树根，对每一个结点用动态规划的方法进行遍历，找出最大连通分支并计算出权值，最后输出最大的连通分支和其权值。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

8、/用结构体来表示结点 long weight; /结点的权值 int father; /结点的父亲结点 int childnum; /结点的儿子个数 long wMax; /结点的最大连通分支权值 bool visited; /该结点是否被访问过int save100;/最大连通分支权值来源;2、动态创建数组表示树Cnode *tree=new Cnoden+1;3、树的初始化for (i=1;i<=n;i+) /树结构初始化并输入数据 treei.father=0; treei.childnum=0; treei.visited=false; cin>>(treei.wei

9、ght); treei.wMax=treei.weight;treei.save0=0;treei.save1=0;treei.save2=0;treei.save3=0;treei.save4=0;treei.save5=0;4、树结构的建立：cout<<"请输入各结点的关系："<<endl;for (i=1;i<=(n-1);i+)/输入数据 cin>>u>>v; treev.father=u; treeu.childnum+; cout<<endl;5、动态规划算法实现计算树的最大连通分支：int ro

10、ot; int m=1;for (i=1;i<=n;i+)/确定树根 if (treei.father=0) root=i; while (treeroot.childnum>0)/遍历树 for (i=1;i<=n;i+) if (treei.childnum=0)&&(!treei.visited) treei.visited=1; treetreei.father.childnum-; if (treei.wMax>0) treetreei.father.wMax=treetreei.father.wMax+treei.wMax; treetree

11、i.father.savei=i;for(int m=0;m<=5;m+) if(treei.savem!=0) treetreei.father.savem=treei.savem; 6、结果的输出long max=tree1.wMax; int h=1;for (i=2;i<=n;i+)/求出最大的连通分支权值 if (treei.wMax>max) max=treei.wMax; h=i;cout <<"最大权值为 ："<<max<<endl;cout<<endl;cout <<"

12、最大连通分支包含的结点为 ："<<endl;for (int j=1;j<=n;j+)if(treeh.savej!=0)cout<<treeh.savej<<endl;if(j=h)cout<<h<<endl;4.2流程设计总体设计的流程图如图4.1所示：开始初始化树动态规划求最大连通分支计算最大权值输出结果完成未完成建立树结构图4.1 总体流程图5 模块分析5.1 树的存储模块代码分析：struct Cnode /用结构体来表示结点 long weight; /结点的权值 int father; /结点的父亲结点

13、int childnum; /结点的儿子个数 long wMax; /结点的最大连通分支权值 bool visited; /该结点是否被访问过int save100;/最大连通分支权值来源; 树的初始化及建立：cout<<"请输入树结点的个数 "<<endl<<"n= "cin>>n; cout<<endl;Cnode *tree=new Cnoden+1;/动态创建数组表示树 cout<<"请依次输入各结点的权值："<<endl;for (i=1;i

14、<=n;i+) /树结构初始化并输入数据 treei.father=0; treei.childnum=0; treei.visited=false; cin>>(treei.weight); treei.wMax=treei.weight;treei.save0=0;treei.save1=0;treei.save2=0;treei.save3=0;treei.save4=0;treei.save5=0;cout<<endl; cout<<"请输入各结点的关系："<<endl;for (i=1;i<=(n-1);

15、i+)/输入数据 cin>>u>>v; treev.father=u; treeu.childnum+; 5.2 计算树的最大连通分支模块代码分析：int root; int m=1;for (i=1;i<=n;i+)/确定树根 if (treei.father=0) root=i; while (treeroot.childnum>0)/遍历树 for (i=1;i<=n;i+) if (treei.childnum=0)&&(!treei.visited) treei.visited=1; treetreei.father.chil

16、dnum-; if (treei.wMax>0) treetreei.father.wMax=treetreei.father.wMax+treei.wMax; treetreei.father.savei=i;for(int m=0;m<=5;m+) if(treei.savem!=0) treetreei.father.savem=treei.savem; long max=tree1.wMax; int h=1;for (i=2;i<=n;i+)/求出最大的连通分支权值 if (treei.wMax>max) max=treei.wMax; h=i;cout &l

17、t;<"最大权值为 ："<<max<<endl;cout<<endl;cout <<"最大连通分支包含的结点为 ："<<endl;for (int j=1;j<=n;j+)if(treeh.savej!=0)cout<<treeh.savej<<endl;if(j=h)cout<<h<<endl;6 系统测试程序完成后需要对程序进行测试，在本程序中需要输入树结点的个数，各结点的权值，各节点之间的对应关系，最后即可输出相应的结果。输入树的

18、实例如图6-1所示，输入过程和输入结果如6-2到6-5所示： -131-1112345图6-1 输入实例图6-2输入树结点的个数图6-3 输入各结点的权值图6-4 各结点的对应关系每行有表示树T的一条 边的2个整数u,v，表示顶点u与顶点v相连图6-5树的结构图图6-6计算出得最大权值及包含的结点图6-7最大连通分支从上述结果可知，此程序能够很好地解决树的最大连通分支问题，从最终的结果来看此次设计还是比较成功的。上面显示的就是计算树的最大连通分支的问题从例子可以看出，我们输入相应的数据后可以一目了然的看到最终的结果，不用看太多的复杂关系，能给我们一种简洁明了的感觉，但从用户体验上来看，界面不够

19、友好，只是大体的显示了结构，从另外一方面讲显得很抽象，因此这点需要改进。7 结论本次课程设计用C+进行开发，采用了动态规划算法。动态规划算法和递归算法是在解决很多问题中比较通用的算法，此次课程设计通过动态规划算法和递归能成功地解决树的最大连通分支问题。经过此次对次问题的解决，再次加深了我对动态规划这种思想的理解。刚开始选题的时候觉得很简单，能够很容易的去实现，但是仔细想后，发现并不是想象中的那样子，甚至无从下手。虽然树的最大连通分支问题是用动态规划实现的一个很好的例子，但是真正去实现的人并不多，因此可供参考的资料很少。通过查阅资料，知道了几种解决此问题的方法，其中比较有名的为蛮力算法和动态规划

20、算法，但综合其时间效率和实现过程，最后选择了动态规划。在程序设计时，使用了结构体来存储树的各节点的信息，也使用了数组来表示数。此程序有以下几大优点：1、代码简练易懂；2、方便用户使用；3、能成功地解决树的最大连通分支问题。当然由于时间比较紧，再加上有些基础知识的原因，只是大体实现了功能，界面之类的不够友好，需要在下来的时间不断钻研，刻苦学习，争取能够学到更多的东西，让自己变得更好。8 致谢首先需要感谢的是指导老师王晓明老师，在他的督促下才能按时完成这个课程设计，感谢他这学期对我们的细心教导与帮助，在他的帮助下我虽不能说学到了全部的知识，但收获却不少，让我很好的理解了算法设计与分析这门课程的重要

21、性，给我以后在遇到问题的时候提供了很多的思路。王老师总是很对我们提出各种问题很热情耐心的解答。没有他的帮助与辅导我们是不可能完成学习和课程设计的。再者需要感谢的是与我们相关的各门课的老师，没有他们，我们就不会有很好的基础做课程设计了。当然整个完成的过程中周围的同学也给了不少帮助，总之在此真的非常感激每个人！有进步是因为有帮助！9 参考文献1宋文. 算法设计与分析. 重庆：重庆大学出版社，20012Anany Levitin. 算法设计与分析基础. 北京：清华大学出版社，20063王晓东. 算法设计与实验题解M.北京：电子工业出版社，20064王红梅. 算法设计与分析M.北京：清华大学出版社，2

22、0065郑晓明. 算法设计与分析M.北京：清华大学出版社，2005附录#include "iostream.h" #include <fstream> using namespace std; struct Cnode /用结构体来表示结点 long weight; /结点的权值 int father; /结点的父亲结点 int childnum; /结点的儿子个数 long wMax; /结点的最大连通分支权值 bool visited; /该结点是否被访问过int save100;/最大连通分支权值来源; int main() int i; long n,u

23、,v;cout<<"请输入树结点的个数 "<<endl<<"n= "cin>>n; cout<<endl;Cnode *tree=new Cnoden+1;/动态创建数组表示树 cout<<"请依次输入各结点的权值："<<endl;for (i=1;i<=n;i+) /树结构初始化并输入数据 treei.father=0; treei.childnum=0; treei.visited=false; cin>>(treei.weigh

24、t); treei.wMax=treei.weight;treei.save0=0;treei.save1=0;treei.save2=0;treei.save3=0;treei.save4=0;treei.save5=0;cout<<endl; cout<<"请输入各结点的关系："<<endl;for (i=1;i<=(n-1);i+)/输入数据 cin>>u>>v; treev.father=u; treeu.childnum+; cout<<endl;cout<<endl; co

25、ut<<"树的结构如下图所示 ："<<endl;cout<<"*"<<endl;cout<<".4(1)."<<endl; cout<<".*.*."<<endl; cout<<".*.*."<<endl; cout<<".*.*."<<endl;cout<<".*.*."<<endl; c

26、out<<".1(-1).5(-1)."<<endl; cout<<".*.*."<<endl; cout<<".*.*."<<endl;cout<<".*.*."<<endl;cout<<".*.*."<<endl;cout<<".2(1).3(3)."<<endl;cout<<"."<<

27、endl;cout<<"*"<<endl;cout<<endl;cout<<endl;int root; int m=1;for (i=1;i<=n;i+)/确定树根 if (treei.father=0) root=i; while (treeroot.childnum>0)/遍历树 for (i=1;i<=n;i+) if (treei.childnum=0)&&(!treei.visited) treei.visited=1; treetreei.father.childnum-; if (treei.wMax>0) treetreei.father.wMax=treetreei.father.wMax+treei.wMax; treetreei.father.savei=i;for(int m=0;m<=5;m+) if(treei.savem!=0) treetreei.father.savem=treei.savem; long max=tree1.wMax; int h=1;for (i=2;i<=n;i+)/求出最大的连通分支权值 if (treei.wMax>max) max=treei.wMax; h=