ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 效率神器,一键搞定繁琐工作
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: lee1892

[讨论] 来个难度高点的:用最快的方法找出一个树内距离最远的两个节点间的距离

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2014-12-5 17:03 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
本帖最后由 yiyiyicz 于 2014-12-5 18:21 编辑

代码见70楼,图见68楼
测试见附件

思路描述看前面的回帖。用的是自下而上的方式
最大路径长度为103,路径经过的结点26,24,21,19,3,4,5,7,11。也就是两个叶结点26,11之间的路径,经过根结点1
树形图是随意画的,这个结果不代表最长路径一定要结果根结点1。比如可以把叶节点或者中间结点边的权值加大,就可以看到不需要经过根结点的最长路径。
代码只是找出一条最长路径。修改后,也可以找出所有的最大路径,及其所有路径
代码是用msxml写的。基本上没用XPath语句(用XPath的地方已经标出,这个也可以不用)。代码还可以加速
忘了说明:代码中没有加压缩树形图功能。如果会msxml,这个不难
这样,似乎需要修改代码才能适应没有压缩的树形图。不过这样将大大增加代码执行速度
所以,修改代码时注意要用压缩后的树形图
所谓压缩,就是把没有分叉的结点,统统用边的权值代表

调试时可以变更附件的sheet1中A/B两列的数据,观察结果。切记,修改数据不可违反树形图的规则
sheet1右侧的数据是调试中记录下来的,可以参考
附件
xmltree.rar (60.95 KB, 下载次数: 58)

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-12-5 17:23 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
yiyiyicz 发表于 2014-12-5 16:55

你最好用17楼、34楼、35楼的代码作为树的输入,这样容易对比。

TA的精华主题

TA的得分主题

发表于 2014-12-5 18:13 | 显示全部楼层
lee1892 发表于 2014-12-5 17:23
你最好用17楼、34楼、35楼的代码作为树的输入,这样容易对比。

我没有看出你所说的符合树形图的规则
而且35楼的下头有人指出了问题
“一个儿子怎么能有两个爸爸”
一定要遵守:一个结点只能有一个父结点

点评

这个嘛,你不看人家的回帖的吗?  发表于 2014-12-6 15:20

TA的精华主题

TA的得分主题

发表于 2014-12-5 18:15 | 显示全部楼层
上面的代码,似乎应该检查:父结点有几个

点评

那几楼的代码您看了吗?看明白没?  发表于 2014-12-6 20:31
  发表于 2014-12-6 20:30

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-12-5 18:33 来自手机 | 显示全部楼层
yiyiyicz 发表于 2014-12-5 18:15
上面的代码,似乎应该检查:父结点有几个

很简单呀,你就认为一个连接里,数字小的那个是父节点好了。

点评

有没有防止结点编号重复?  发表于 2014-12-5 19:22

TA的精华主题

TA的得分主题

发表于 2014-12-5 19:19 | 显示全部楼层
lee1892 发表于 2014-12-5 18:33
很简单呀,你就认为一个连接里,数字小的那个是父节点好了。

如果这样,你就按照sheet1中,父子关系的格式(A/B两列),生成数据(参考那张图)
如果不熟悉MSXML,可以用treeview控件,把没有分叉的统统转换成边的权值,然后用我的代码算一下,看看结果对不对

点评

你的代码谁能改啊,还是你自己来吧  发表于 2014-12-6 11:05

TA的精华主题

TA的得分主题

发表于 2014-12-6 11:20 | 显示全部楼层
这个代码不困难吧,几乎没有XPath
如果是算一下,下载附件,在sheet1中放入数据就可以了
其实,你需要的是测试你的想法。只用随机生成的数据,怎么会正好符合一些极端的设想呢?
如果说要测试速度,那就是另外的事情了
我的代码,如果有一连串的没有分叉的结点,会出错。这时可以修改代码,在两层for循环之前改一下父节点下子节点集合那里改;或者把两层for循环改成一层,仅仅比较子节点的edge属性值大小,一层循环需要功夫了,这里就可以把没有分叉的结点考虑进去;或者在生成xml树后面,再处理压缩
前面的树生成代码,不能保证所有结点只有一个父节点

点评

自己知道有错还不改吗?  发表于 2014-12-6 15:19

TA的精华主题

TA的得分主题

发表于 2014-12-6 17:02 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
我的代码有错误,坐等证明!
没工夫陪你

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-12-6 20:29 | 显示全部楼层
yiyiyicz 发表于 2014-12-6 17:02
我的代码有错误,坐等证明!
没工夫陪你

这不是你的原话吗?
我的代码,如果有一连串的没有分叉的结点,会出错。


你这爱好还真是......口味独特的紧

我是不是应该说求求你陪陪我嘛?

点评

弄懂图的问题需要足够的想象能力。代码的问题已经反复说明过,不该看不懂吧?!  发表于 2014-12-6 22:27

TA的精华主题

TA的得分主题

发表于 2015-7-28 09:43 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
好精彩的论战!{:soso_e163:}
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-11-19 12:20 , Processed in 0.038099 second(s), 15 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表