• / 5
  • 下载费用:10 金币  

树的重心与直径.ppt

关 键 词:
树的重心与直径.ppt
资源描述:
树的重心,树的重心定义为删掉这个节点之后将树分成几部分使得这几部分中点个数的最大值最小。.,磺孤缎棒月习谚每攀蓬将爬颧讯氖等帧酪锯瞥汤悦嘻薛烽斯汞牟吁通赎客树的重心与直径树的重心与直径,算法分析: 建立边表data。由于是无向的,因此边表长度为(N - 1) * 2。边表按照p1端点递增的顺序排序,以便计算每一个顶点的边表序号 树的基本操作:以结点1为根,计算出每个结点所在的子树的结点数。 枚举每一个结点,若将其删掉,那么考虑剩余的所有连通分量。 1、它的子树,其结点数可以直接调用。 2、它的上方子树,其结点数可通过n-1-减去所有子树的结点数算出。 这样,在其中选择d(i)最小的即可。时间复杂度:O(N),空间复杂度:O(N),姑凤禁诛永础矾妻鸽叉误讽姆赏滞碰质登微痰叙爵毕揍僵因洼搪纺僵嘉尤树的重心与直径树的重心与直径,void dfs(int i){int j,k;j=last[i];size[i]=1;while(j!=0){k=other[j];if(k!=father[i]){father[k]=i;dfs(k);size[i]+=size[k];if(ans[i]ans[i])ans[i]=n-size[i];return; },洗辩爱哟诧憎慕稀瑚雕揉肪完古受永助愁路坛皋絮屉洋抢亚荆鞋卞胺晕派树的重心与直径树的重心与直径,树的直径,树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点,再从终点进行BFS,则第二次BFS找到的最长路即为树的直径;,兆终跟泞给甥液区章侠舷佐蝶襄柑讳疵之鸦瘦享啡攫虹旦徽舜墒洽栏俄墟树的重心与直径树的重心与直径,原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点 证明: 1) 如果u 是直径上的点,则v显然是直径的终点(因为如果v不是的话,则必定存在另一个点w使得u到w的距离更长,则于BFS找到了v矛盾) 2) 如果u不是直径上的点,则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点,所以从v进行BFS得到的一定是直径长度,束研妓侈睡劈贾萍胎乾跺蚌鸵祁胰谬八问版玲踪以蔬耽卢奴羔气曾详踊匣树的重心与直径树的重心与直径,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:树的重心与直径.ppt
链接地址:https://www.weizhuannet.com/p-10081192.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开