来个难度高点的：用最快的方法找出一个树内距离最远的两个节点间的距离

incognito · 发表于 2015-10-13 05:51

lee1892 发表于 2014-12-6 20:29
这不是你的原话吗？

别吵啦，图论不更新啦？

好像，这个就是算图的直径麽。

yiyiyicz · 发表于 2015-10-13 20:03

本帖最后由 yiyiyicz 于 2015-10-13 20:09 编辑

怎么又被翻出来了？
其实这里面有两点需要注意
1，解决图的问题，需要有足够的几何空间想象力，平面的、立体的，还有拓扑。如果缺乏这种想象力，单纯的用一些方法去套，往往是事倍功半，甚至失败。VBA板块就有这样额例子。就像解决力学问题，生搬硬套物理-数学方法，而不在概念上深入讨论，那解法将会一塌糊涂
2，用xml，是因为他适用树形结构。并非所有的图用xml方法都能有这样简单
另外，随着计算机应用深入，图、矩阵的作用越来越大。比如智能导航。

下标越界 · 发表于 2015-10-13 20:46

本帖最后由下标越界于 2015-10-13 20:52 编辑

kangatang 发表于 2014-11-18 12:25
弱弱地问一句，可以应用在哪里？有应用才有价值，有价值才有动力

我能想到的应用就是高分子化学中对链烃的系统命名法，需要先找出主链（最长的碳链，然后依次确定各支链的长度）。比如异辛烷，系统命名法改叫作2,2,4—三甲基戊烷。

incognito · 发表于 2015-10-13 22:01

下标越界发表于 2015-10-13 20:46
我能想到的应用就是高分子化学中对链烃的系统命名法，需要先找出主链（最长的碳链，然后依次确定各支链的 ...

太强悍了，完全看不懂。

incognito · 发表于 2015-10-14 09:04

yiyiyicz 发表于 2015-10-13 20:03
怎么又被翻出来了？
其实这里面有两点需要注意
1，解决图的问题，需要有足够的几何空间想象力，平面的、 ...

xml效率如何，假设随机1万节点树，

nervfwg · 发表于 2015-10-14 13:56

我是来看小说的......

kangatang · 发表于 2015-10-26 21:25

下标越界发表于 2015-10-13 20:46
我能想到的应用就是高分子化学中对链烃的系统命名法，需要先找出主链（最长的碳链，然后依次确定各支链的 ...

曾经也是有机化学，这门课有点像玩积木。

jsgj2023 · 发表于 2017-5-14 11:58

好精彩,我就抄抄代码以提升打字速度!

aimisiyou · 发表于 2020-3-27 00:35

本帖最后由 aimisiyou 于 2020-3-27 00:44 编辑

lee1892 发表于 2014-11-21 14:22
这个题目，我基本上就是按之前的几个提示来分析的：
1、明确题目中的树是这样的一个图：
不存在孤立 ...

a情况基本理解了。b情况还需消化下。佩服证明的巧妙性和全面性，刚好需要处理树中最远距离的两个叶子节点问题。

aimisiyou · 发表于 2020-3-27 09:21

本帖最后由 aimisiyou 于 2020-3-27 09:29 编辑

有了你的这个证明，可以大大减少运行时间。一开始我的方法是最远距离肯定是两个叶子节点，然后找出所有叶子结点，求所有两个叶子结点的距离，找出最大距离值。两个叶子结点的距离就是分别向上找父节点，碰到第一个公共父节点时停止，此时两个叶子节点的距离就是两者到公共父节点距离之和。当然，叶子结点较多时，运行时间长些，因为是穷举任意两个叶子结点的距离找最大值。

		自动登录	找回密码
密码			免费注册

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