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

wcymiss · 发表于 2014-11-21 09:56

本帖最后由 wcymiss 于 2014-11-21 10:32 编辑

Moneky 发表于 2014-11-21 09:53
4;2,1;3,1;2,4
这是什么意思？
3 2

你应该这样看：                或者这样：                                     再或者这样：                               这样也行：

      1                                     2                                                 3                                              4
      /  \                                  / \                                              /                                              /
   2    3                               4    1                                           1                                              2
   /                                              \                                        /                                              /
4                                                 3                                     2                                              1
                                                                                             /                                              /
                                                                                             4                                           3

wcymiss · 发表于 2014-11-21 10:18

Moneky 发表于 2014-11-20 16:30
先扔一块砖。
无脑穷举法，基本上3分钟内可以求出（用附件中的代码生成的数据），没有仔细看过数据，但怎么 ...

楼主没说逗号前面是父，后面是子啊。

Moneky · 发表于 2014-11-21 10:24

wcymiss 发表于 2014-11-21 10:18
楼主没说逗号前面是父，后面是子啊。

没有说也得统一啊，你前面发的 ××××2$就是那样的

wcymiss · 发表于 2014-11-21 10:31

Moneky 发表于 2014-11-21 10:24
没有说也得统一啊，你前面发的 ××××2$就是那样的

看9楼我的提问和楼主10楼的回复

Moneky · 发表于 2014-11-21 10:45

wcymiss 发表于 2014-11-21 10:31
看9楼我的提问和楼主10楼的回复

我理解错了，其实逗号只表示两个点相连。不看成什么父父子子君君臣臣的。

wcymiss · 发表于 2014-11-21 12:28

本帖最后由 wcymiss 于 2014-11-24 08:21 编辑

.............................................................

lee1892 · 发表于 2014-11-21 14:22

本帖最后由 lee1892 于 2014-11-21 15:10 编辑

这个题目，我基本上就是按之前的几个提示来分析的：
1、明确题目中的树是这样的一个图：
不存在孤立节点，不存在回路即任一节点到另一个节点必然存在且仅存在唯一路径（经过的边不重复）
2、基于以上特点，就可以回答前面提示的第三个问题，任一节点都可以视作根节点。
3、对于提示的第二个问题，前面有人给出了实例给予了否定。那么进一步的猜测，就是既然距离最远的两节点不一定都是距离根节点最远的，那么是不是有一个必然是？试证明如下：
假设根节点为O，相互距离最远的两节点分别为 P1 和 P2，而存在一个距离根节点 O 更远的一个节点，设为 Q，如果我们能够证明 Q 到 P1 或 P2 的距离必有一个大于 P1 到 P2 的距离，就可以证明前面的猜测是正确的。记 P1 到 P2 的距离为：|P1 - P2|，类似的 |O - Q|...
有：|O - Q| > |O - P1|，|O - Q| > |O - P2|
由上述 1 知，P1 到 P2 的路径必然经过其共有上溯节点，设为 A，则 |P1 - A| <= |P1 - O|，|P2 - A| <= |P2 - O|
有：|P2 - P1| = |P2 - A| + |A - P1|
有如下两种情况：
a、Q 到 O 不经过 A，则 |Q - P1| = |Q - A| + |A - P1|
      如果 Q 到 A 经过 O，则 |Q - A| = |Q - O| + |O - A| > |P2 - O| >= |P2 - A|，所以 |Q - P1| > |P2 - P1|
      如果 Q 到 A 不经过 O，则 Q、A 必然有一个共有上溯节点 B，B 为 A 到 O 间的一个节点，于是 |Q - A| = |Q - B| + |B - A| = |Q - O| - |O - B| + |B - A|
            而 |P2 - A| = |P2 - B| - |B - A| = |P2 - O| - |O - B| - |B - A|，所以 |Q - A| > |P2 - A|，所以 |Q - P1| > |P2 - P1|
b、Q 到 O 经过 A，则有两种可能：
      Q 在 A 到 P1 或 P2 的某条分支上的分支，设为 P2，设 Q 和 P2 的共有上溯节点为 B，则 |Q - P1| = |Q - B| + |B - A| + |A - P1| = |Q - O| - |O - B| + |B - A| + |A - P1|
            而 |P2 - A| = |P2 - O| - |O - B| + |B - A| ........
      Q 与 P1、P2 的共有上溯节点为 A，则 |Q - P1| = |Q - A| + |A - P1| = |Q - O| - |O - A| + |A - P1| .........
4、既然距离最远的两个节点必有一个距离根节点最远，就可以以任一节点开始，先找到距离其最远的节点，再由此节点始再次找到与其最远的节点，就可以获得距离最远的两个节点的距离了。

最终，问题归结为如何最快的找到距离根节点最远的节点

注：共有上溯节点指两个节点到根节点的路径中的第一个共有节点。
以上。

lee1892 · 发表于 2014-11-21 14:58

本帖最后由 lee1892 于 2014-11-21 15:06 编辑

一个广度优先的遍历查找，利用队列来实现迭代计算：

Public Function LongestPath(ByVal strTree As String) As Long
Dim nSize&, aData, aTree(), i&, aCnt&(), nA&, nB&, aTemp&()
aData = Split(strTree, ";")
nSize = CInt(aData(0)) ' 第一个元素为节点数量
ReDim aTree(1 To nSize), aCnt(1 To nSize)
For i = 1 To nSize
ReDim aTemp(1 To nSize)
aTree(i) = aTemp ' 建立复合数组
Next
For i = 1 To UBound(aData)
nA = CInt(Split(aData(i), ",")(0)): nB = CInt(Split(aData(i), ",")(1))
' 相互连接的两节点的编号
aCnt(nA) = aCnt(nA) + 1: aCnt(nB) = aCnt(nB) + 1
' 某节点的连接节点数量计数
aTree(nA)(aCnt(nA)) = nB: aTree(nB)(aCnt(nB)) = nA
' 建立连接
Next
ReDim aTemp(1 To nSize) ' 临时数组重置用以记录节点到根节点的距离
nA = BFS_Iterative(aTree, aCnt, 1, aTemp) ' 距离根节点 1# 最远的节点编号
ReDim aTemp(1 To nSize) ' 重置临时数组
nB = BFS_Iterative(aTree, aCnt, nA, aTemp) ' 距离根节点 nA 最远的节点编号
LongestPath = aTemp(nB) ' 返回距离值
Erase aTree: Erase aTemp: Erase aCnt: Erase aData
End Function
Private Function BFS_Iterative&(ByRef aTree(), ByRef aCnt&(), ByVal nInd&, ByRef aDist&())
' aTree：以元素下标为节点编号的数组，其元素为该节点所连接的节点编号的数组
' aCnt：以元素下标为节点编号的数组，其元素为该节点所连接的节点的数量
' nInd：当前遍历的起始节点编号
' aDist：以元素下标为节点编号的数组，其元素为该节点至起始节点的距离值
' 返回值：距离起始节点最远的节点编号
Dim i&, nCurInd&, nMaxDist&, nMInd&
Dim aPathed() As Boolean
Dim cQue As New Collection
ReDim aPathed(1 To UBound(aTree)) ' 记录某节点是否已经查找过
aPathed(nInd) = True ' 起始节点设置为已查找过
cQue.Add nInd ' 用集合模拟队列，添加起始节点进入队列
While cQue.Count > 0 ' 当队列不为空时循环
nCurInd = cQue(1) ' 当前节点为队列中的第一个节点
cQue.Remove 1 ' 删除队列中的第一个节点
aPathed(nCurInd) = True ' 设置当前节点为已查找过
For i = 1 To aCnt(nCurInd) ' 遍历查找当前节点的连接节点
If Not aPathed(aTree(nCurInd)(i)) Then ' 如果该连接节点未查找过，则
cQue.Add aTree(nCurInd)(i) ' 将该连接节点添加到队列中
aDist(aTree(nCurInd)(i)) = aDist(nCurInd) + 1 ' 该连接节点距起始节点的距离为当前节点的距离 + 1
End If
Next
Wend
' 找到距离起始节点最远的节点编号
For i = 1 To UBound(aDist)
If aDist(i) > nMaxDist Then nMaxDist = aDist(i): nMInd = i
Next
BFS_Iterative = nMInd
Set cQue = Nothing
End Function

复制代码

wcymiss · 发表于 2014-11-21 22:08

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

看到你这一大段 O 啊 P 啊 Q的我就晕了。

我只记得小时候玩钥匙圈，一大堆钥匙圈串在一起，拎起其中一个，找到垂得最低的那个圈，再拎起这个圈，就能找到最长的链子。原理要我证明的话，可能会非常啰嗦。

我那个是“深度优先递归”么？我不晓得什么是“深度优先”、“广度优先”，只是听说过这个名词。

递归溢出刚测了下，没有分叉的5000个节点溢出，4999个可以运行。

改成非递归的：

Private Sub GetNodeLenght2(NodeIndex As Integer, NodeLength As Integer)
Dim i As Integer
Dim j As Integer
Dim N As Integer
Dim arr(), intPos As Integer
ReDim arr(1 To UBound(arrTree))
intPos = 1
arr(intPos) = NodeIndex
arrNodeLength(NodeIndex) = NodeLength
Do
i = i + 1
For j = 1 To arrNodeCount(arr(i))
N = arrTree(arr(i))(j)
If arrNodeLength(N) = 0 Then
arrNodeLength(N) = arrNodeLength(arr(i)) + 1
intPos = intPos + 1
arr(intPos) = N
End If
Next
Loop Until i = intPos
MaxLength = arrNodeLength(arr(i))
MaxNodeIndex = arr(i)
End Sub

复制代码

lee1892 · 发表于 2014-11-22 00:46

wcymiss 发表于 2014-11-21 22:08
看到你这一大段 O 啊 P 啊 Q的我就晕了。

我只记得小时候玩钥匙圈，一大堆钥匙圈串在一起，拎起其中一 ...

这个题里我最得意的就是题目分析乐，再就是这个证明了，我觉得这是我能做到的最好的数学描述了[得意]

总不能说就是就是嘛～

溢出的问题我没试，但估计10000层递归怎么也干掉了，果然言中，嘿嘿～

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

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

点评

点评

点评

评分

点评