树最大连通分支问题.ppt_第1页
树最大连通分支问题.ppt_第2页
树最大连通分支问题.ppt_第3页
树最大连通分支问题.ppt_第4页
树最大连通分支问题.ppt_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

树的最大连通 分支问题,问题描述：,给定一棵树T，树中每个顶点u都有一个权w(u)，权可以是负数。现在要找到树T的一个连通子图使该子图的权之和最大。,对于给定的树T，编程计算树T的 最大连通分支。,编程任务：,第1行有1个正整数n，表示树T有n个顶点。 树T的顶点编号为1，n。 第2行有n个整数，表示n个顶点的权值。 接下来的n-1行中，每行有表示树T的一条 边的2个整数u,v，表示顶点u与顶点v相连。,数据输入：,由文件input.txt给出输入数据。,结果输出：,将计算出的最大连通分支的权值输出 到文件output.txt。,input.txt： 5 -1 1 3 1 -1 4 1 1 3 1 2 4 5,输入文件示例：,1,2,3,4,5,-1,3,1,-1,1,最大连通分支 连通图 连通图中各结点的权值之和最大,输出文件示例：,output.txt: 4,1,2,3,4,-1,3,1,1,树根,root,T1,T2,W0,W0,最大连通分支在子树或树中，因此对树进行遍历，依次求出以每个结点为树根的最大连通分支权值。,Wr=Wr+Wt1,root,T1,T2,W0,W0,算法分析:,问题具有两个子性质:,最优子结构性质 子问题重叠性质,树根,root,T1,T2,W0,W0,算法实现:,1,2,3,4,5,3,1,-1,1,树根,-1,对于叶子结点或儿子个数为0的 结点，其最大连通分支权值为该 结点的权值 某一结点的最大连通权值0， 则将其值加到它的父亲结点的最 大连通权值，反之舍弃该值 最后求出根结点的最大连通权 值，结束遍历 所求最大连通分支权值即结点中 的最大连通权值,数据结构,struct Cnode long weight; /结点的权值 int father; /该结点的父亲结点 int childnum; /结点的儿子数 long wMax; /结点的最大连通分支的权值 bool visited; /该结点是否被访问过 ;,动态创建数组表示树 Cnode *tree=new Cnoden+1; 存储记录初始化及数据输入 for (i=1;i(treei.weight);,算法步骤(1),for (i=1;iuv; treev.father=u; treeu.childnum+; ,treei.wMax=treei.weight; ,确定树根 for (i=1;i0 for (i=1;i0) treetreei.father.wMax=treetreei.fat
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论