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

lee1892

两次 深度优先，迭代计算，数组模拟堆栈

1. Private aTree()
   
2. Private aDist%()
   
3. Private aCnt%()
   
4. Private nSize%
   
5. Public Function LongestPath(ByVal strTree As String) As Long
   
6.     Dim aData, i%, nA%, nB%, aLnk
   
7.     aData = Split(strTree, ";")
   
8.     nSize = CInt(aData(0))
   
9.     ReDim aTree(1 To nSize), aCnt(1 To nSize), aDist(1 To nSize)
   
10.     For i = 1 To nSize
    
11.         aTree(i) = aDist
    
12.     Next
    
13.     For i = 1 To UBound(aData)
    
14.         aLnk = Split(aData(i), ",")
    
15.         nA = aLnk(0)
    
16.         nB = aLnk(1)
    
17.         aCnt(nA) = aCnt(nA) + 1
    
18.         aCnt(nB) = aCnt(nB) + 1
    
19.         aTree(nA)(aCnt(nA)) = nB
    
20.         aTree(nB)(aCnt(nB)) = nA
    
21.     Next
    
22.     nA = DFS_Iterative(1)
    
23.     ReDim aDist(1 To nSize)
    
24.     nB = DFS_Iterative(nA)
    
25.     LongestPath = aDist(nB)
    
26.     Erase aTree: Erase aDist: Erase aCnt
    
27. End Function
    
28. 
    
29. Private Function DFS_Iterative%(nInd%)
    
30.     Dim i%, nCurInd%, nMaxLen%, nMaxInd%
    
31.     Dim aStack%(), nStackInd%
    
32.     ReDim aStack(1 To nSize, 1 To 2)
    
33.     aDist(nInd) = 1
    
34.     nStackInd = 1
    
35.     aStack(1, 1) = nInd
    
36.     aStack(1, 2) = 1
    
37.     Do
    
38.         nCurInd = aStack(nStackInd, 1)
    
39.         For i = aStack(nStackInd, 2) To aCnt(nCurInd)
    
40.             If aDist(aTree(nCurInd)(i)) = 0 Then Exit For
    
41.         Next
    
42.         If i > aCnt(nCurInd) Then
    
43.             nStackInd = nStackInd - 1
    
44.         Else
    
45.             nCurInd = aTree(nCurInd)(i)
    
46.             aDist(nCurInd) = nStackInd
    
47.             If nStackInd > nMaxLen Then nMaxLen = nStackInd: nMaxInd = nCurInd
    
48.             nStackInd = nStackInd + 1
    
49.             aStack(nStackInd, 1) = nCurInd
    
50.             aStack(nStackInd, 2) = 1
    
51.             aStack(nStackInd - 1, 2) = i + 1
    
52.         End If
    
53.     Loop Until nStackInd = 0
    
54.     DFS_Iterative = nMaxInd
    
55. End Function

复制代码

lee1892

一次 深度优先，递归计算，方法一，线性树会溢出

1. Private aTree()
   
2. Private aCnt%()
   
3. Private nSize%
   
4. Private aPathed() As Boolean
   
5. Public Function LongestPath(ByVal strTree As String) As Long
   
6.     Dim aData, i%, nA%, nB%, aLnk, aTemp%()
   
7.     aData = Split(strTree, ";"):    nSize = CInt(aData(0))
   
8.     ReDim aTree(1 To nSize), aCnt(1 To nSize), aPathed(1 To nSize), aTemp(1 To nSize)
   
9.     For i = 1 To nSize: aTree(i) = aTemp:   Next
   
10.     For i = 1 To UBound(aData)
    
11.         aLnk = Split(aData(i), ",")
    
12.         nA = aLnk(0):               nB = aLnk(1)
    
13.         aCnt(nA) = aCnt(nA) + 1:    aCnt(nB) = aCnt(nB) + 1
    
14.         aTree(nA)(aCnt(nA)) = nB:   aTree(nB)(aCnt(nB)) = nA
    
15.     Next
    
16.     LongestPath = DFS_Recursive(1)(1)
    
17.     Erase aTree: Erase aCnt: Erase aPathed
    
18. End Function
    
19. Private Function DFS_Recursive(nInd%)
    
20.     Dim nDist1%, nDist2%, i%, nChdInd%, aDist%(1), aChild
    
21.     If aPathed(nInd) Then: DFS_Recursive = aDist: Exit Function
    
22.     aPathed(nInd) = True
    
23.     For i = 1 To aCnt(nInd)
    
24.         nChdInd = aTree(nInd)(i)
    
25.         If Not aPathed(nChdInd) Then
    
26.             aChild = DFS_Recursive(nChdInd)
    
27.             If aChild(0) + 1 > nDist1 Then
    
28.                 nDist2 = nDist1: nDist1 = aChild(0) + 1
    
29.             ElseIf aChild(0) + 1 > nDist2 Then
    
30.                 nDist2 = aChild(0) + 1
    
31.             End If
    
32.             If aChild(1) > aDist(1) Then aDist(1) = aChild(1)
    
33.         End If
    
34.     Next
    
35.     If nDist1 + nDist2 > aDist(1) Then aDist(1) = nDist1 + nDist2
    
36.     aDist(0) = nDist1: DFS_Recursive = aDist
    
37. End Function

复制代码

lee1892

一次 深度优先，递归计算，方法二，线性树会溢出

1. Private aTree()
   
2. Private aCnt%()
   
3. Private aPathed() As Boolean
   
4. Private nSize%
   
5. Private nMaxLen%
   
6. Public Function LongestPath(ByVal strTree As String) As Long
   
7.     Dim aData, i%, nA%, nB%, aLnk, aTemp%()
   
8.     aData = Split(strTree, ";"):    nSize = CInt(aData(0))
   
9.     ReDim aTree(1 To nSize), aCnt(1 To nSize), aPathed(1 To nSize), aTemp(1 To nSize)
   
10.     For i = 1 To nSize: aTree(i) = aTemp:   Next
    
11.     For i = 1 To UBound(aData)
    
12.         aLnk = Split(aData(i), ",")
    
13.         nA = aLnk(0):               nB = aLnk(1)
    
14.         aCnt(nA) = aCnt(nA) + 1:    aCnt(nB) = aCnt(nB) + 1
    
15.         aTree(nA)(aCnt(nA)) = nB:   aTree(nB)(aCnt(nB)) = nA
    
16.     Next
    
17.     DFS_Recursive 1
    
18.     LongestPath = nMaxLen
    
19.     Erase aTree: Erase aCnt: Erase aPathed
    
20. End Function
    
21. Private Function DFS_Recursive%(nInd%)
    
22.     Dim i%, nDist%, nDist1%, nDist2%, nChdInd%
    
23.     nDist1 = -1: nDist2 = -1
    
24.     aPathed(nInd) = True
    
25.     For i = 1 To aCnt(nInd)
    
26.         nChdInd = aTree(nInd)(i)
    
27.         If Not aPathed(nChdInd) Then
    
28.             nDist = DFS_Recursive(nChdInd)
    
29.             If nDist > nDist1 Then
    
30.                 nDist2 = nDist1: nDist1 = nDist
    
31.             ElseIf nDist > nDist2 Then
    
32.                 nDist2 = nDist
    
33.             End If
    
34.         End If
    
35.     Next
    
36.     If nDist1 + nDist2 + 2 > nMaxLen Then nMaxLen = nDist1 + nDist2 + 2
    
37.     DFS_Recursive = nDist1 + 1
    
38. End Function

复制代码

lee1892

yiyiyicz 发表于 2014-11-14 20:36
这题意义不大
用现成的方法，用深度优先遍历，找没有兄弟的分支；用广度优先，排除公共边
或者将数据转到 ...

经我深入学习，20楼的名次解释如下：


遍历（Traversal）：
指沿着某条搜索路线，依次对树种每个结点均作一次且仅做一次访问。

深度优先遍历（Depth First Search）：
是沿着树的深度便利树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
嗯，先要深度优先搜索，看上去比较靠谱

广度优先遍历（Breadth First Search）：
是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
嗯？不是已经深度优先遍历过了吗？还要来一次呀？不过换成了广度优先，看来这个问题还挺麻烦的~

没有兄弟的分支：
这个真没有...

公共边（猜测是 Common Edge或则Shared Edge）：
这个我只能猜是两个图才会有所谓的公共边吧~

XML（eXtensible Markup Language）：
可扩展标记语言，是一种标记语言。
这个怎么转呢？难道要构造一个文本文件？还是用微软的什么工具在内存中虚拟一个？

Xpath（XML Path Language）：
XML路径语言，它是一种用来确定XML文档中某部分位置的语言。XPath基于XML的树状结构，提供在数据结构树中找寻节点的能力。
不知道是不是有这样的函数：Xpath.Tree.MaxNodeDistance，有的话那真是很方便哟~

邻接矩阵（Adjacency Matrix）：
逻辑结构分为两部分：V和E的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
看上去是构造一个NxN的布尔数组？

拓扑（Topology）：
拓扑学的英文名是Topology，直译是地志学，也就是和研究地形、地貌相类似的有关学科。几何拓扑学是十九世纪形成的一门数学分支，它属于几何学的范畴。有关拓扑学的一些内容早在十八世纪就出现了。那时候发现一些孤立的问题，后来在拓扑学的形成中占着重要的地位。
这有点无厘头了吧~

继承（Inheritance）：
是面向对象软件技术当中的一个概念。如果一个类别A“继承自”另一个类别B，就把这个A称为“B的子类别”，而把B称为“A的父类别”也可以称“B是A的超类”。继承可以使得子类别具有父类别的各种属性和方法，而不需要再次编写相同的代码。在令子类别继承父类别的同时，可以重新定义某些属性，并重写某些方法，即覆盖父类别的原有属性和方法，使其获得与父类别不同的功能。另外，为子类别追加新的属性和方法也是常见的做法。 一般静态的面向对象编程语言，继承属于静态的，意即在子类别的行为在编译期就已经决定，无法在执行期扩充。
这、这、这.......

多层继承（可能是 Multple Layer Inheritance）：
这个也没找到，倒是有多重继承，指的是能从多个对象继承行为和特征。

回调函数（Callback Function）：
回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。回调函数不是由该函数的实现方法直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。
我怀疑是和递归函数搞混了。


您看我学习得认真吧

yiyiyicz

“没有兄弟的分支”，这个可以有
意思就是一个父结点，下面有几个子结点，这几个子结点就是兄弟结点。比如在MSXML中有这样的（node）方法：getpreviosSIBLING()  getnextSIBLING()
没有兄弟的分支，就是没有兄弟结点的树枝，图中就是没有分叉
另外，你要找的最长路径存在各种可能性，可能是父子关系，也可能是兄弟关系。而深度优先搜索不利于寻找兄弟关系，广度优先有利于寻找兄弟关系
“XML"
在VBA中用XML方法很简单，在工具--引用 里，添加一个引用就行了。和用字典一样。参见FIGFIG的帖子
在使用时，只需要建立一个xml树，很方便，当然先得学会MSXML。不难
解析方法中的内容十分丰富，功能也很强大。实际应用比如对于展开BOM，比如类似正则关系搜索，比如构造面向对象的数据库（不是面向关系数据库）
“邻接矩阵”
千万不能理解成布尔关系。如果是布尔关系，那么边的权值怎么办。
矩阵的优势可不仅仅为了计算，更为重要的是建立模型。所以如果没有人给出定理和公式，我们这种不是数学专业出身的就告退了。但是有了，那适应场合就大了
“拓扑（Topology）”，
其实在这里很简单，先看女侠的回帖。意思就是最长路径不一定是经过定义严格的“根结点”，而是中间某个结点。那么也可以把这个“中间结点”看成是根结点。那么在图中，完全可以把“树”的图形变变形，不就变成即满足“根结点”的定义，又是最长路径经过的结点了吗。说白了，就是图得是活的，不然就玩不转了。
“公共边”
好像在你设定的条件里，规定一条边不能用两次。用两次的边不就是公共边吗？
“多层继承”
这可能不太规范，但是在网上常常这样说。多层继承和多根继承是一对概念，方向不一样。在VBA编程的时候，有些情况下，用回调函数可以实现这种继承（这可真是继承了），也叫做委托。
书上说，VB/VBA没有继承，只有多态。这么说有这么说的道理。这在EH中讨论过很多次。但是，这不等于说VBA不能做出继承的效果。“委托”也就是用回调函数，就可以实现这样的目的，而且不用指针（这很重要，因为不推荐用指针）。EH中有这样的帖子，我也发过这样的帖子。有了这个，做出对象、面向对象、继承就变成了可能。这是继承，而不是多态。
回调函数不是递归函数。看看女侠的递归，递归可以不用类模块，回调函数要实现委托，必须用类模块，用implements

另外，你为什么不仔细考虑一下，Dijkstra方法呢？

yiyiyicz

有这样一个思路，供参考
1）生成一个树，不管用什么方法（18楼好像就是吧）
2）将这个树用XML来描述，也就是放进XML中去，建立一个XML树。（这之后，脑子里始终有一个树形图，而且能变化）
3）用XML的方法，将没有分叉（也就是没有兄弟结点）的树枝压缩成一个结点，结点有编号（可以保留原来的一个编号），压缩的长度作为边的权值写到属性里（每个结点可以有n个属性），被压缩的所有结点编号也作为一个属性记录下来。这些属性统统作为那个结点的属性
这时的树形图就变成了每个结点都有分叉（都有兄弟结点）的树形图，而边则有权值。
4）从叶结点开始，从所有的叶节点开始，遍历。难度来了
可以借用深度优先/广度优先搜索的方法，如添加堆栈/队列记录遍历过的点。也可以直接在结点上添加属性来记录（这就是XML的优势）
我想，对于一个父节点+两个子结点，最长路径只有三种可能：一是父和老大；二是父和老二；三是老大和老二。一和二这两种情况，还能进一步发展就是再和爷爷结点联系，继续寻找最长，而老大+老二是最长则就此打住了。比较长短是关键，而各种路径的组合别漏掉。
利用XML的解析方法，你就一圈一圈的找去吧。也就是比较长度，注意这时的边已经是有权值了。
你那个Dijkstra方法的代码，就是漏掉了可能性。所以在某类情况下，给出的结果将会出错。

wcymiss

lee1892 发表于 2014-11-22 13:46
一次 深度优先，递归计算，方法二，线性树会溢出

看来我要去学习下深度和广度优先，再学下迭代和递归的区别。

yiyiyicz

我一圈一圈的找去了～真晕啊
这才哪到哪，晕了就什么都完了
接着56楼再解释
先解释一下几个概念
根结点，就是所有的分叉、结点都是从这里长出来的
叶结点，就是没有分叉了，这个分支到此结束了
边，也就是父子结点之间的连接线。虽然都是父子关系，但是远近可以不一样。不一样的程度用边的权值来表示。


看图
可以把上图看做是由下图演变而来。下图父子关系边值都是1，也就不用写了。而结点编号为两位数的这些结点有个特点，他们没有分叉，一条道走到底，而结点编号为一位数的都是有分叉的，每走一步都需要选择方向（当然，到了叶节点算是到头了，不用选择方向了）。上图把下图压缩了，两位数编号的结点在上图中都没有了，用边的权值表示所谓的长度。当然，每对一位数结点之间的路径是由哪些结点组成，需要把删掉的那些结点依次记录下来。这样做有两个好处，一是下面的分析模型没有了啰啰嗦嗦的东西，更加直观了；二是XML容量有个限制，太大了就太慢了。你要求10000结点，担心太大，所以先减肥。
在SMXML中，结点、属性等可以很方便的添加、编辑、删除。编程不费劲
现在想象一下，10000个结点的树形图经过压缩，出来了。实际上就是56楼的钱三步。这三步很简单，就算没有接触过XML的，也不会费多大事就弄出来了。
第四步开始，才是找最长路径
思路是：整个树形图的特点是由若干个有特点的小部分组合而成的。当一个一个小部分都解决了，则整个树形图就搞定了
有特点的小部分还是琢磨上图。图重新画过在下面。


说明

wcymiss

yiyiyicz 发表于 2014-11-23 07:37
我一圈一圈的找去了～真晕啊
这才哪到哪，晕了就什么都完了
接着56楼再解释

亲，你还是甩代码吧。代码比你这么多文字有意义多了。

yiyiyicz

接58楼，58楼编辑太困难了
看红色虚线内，也就是第一步
分析压缩后的三个结点，他们的路径长度只可能有三种可能：绿色、紫色、蓝色。如果是紫色、蓝色，他还会与爷爷结点联系后，继续分析；如果是绿色，那就只剩下比较长短了
分析后，需要记录下来有用的结果。用以继续的分析
这些完成后，将已经分析过的结点删掉，这样新结点就暴露出来了
照此将所有的叶节点统统过一遍
再照上面的过程，对新暴露出来的叶节点，统统来一遍
直到处理完所有的结点
不知一圈一圈的找，意思清楚不？？？？？？？？

这样分析，不会出现漏洞（这页中的代码这么短，我猜有漏洞）
但是，他会涉及根节点，搜索的方式需要注意（主要是MSXML编程）
还有一些需要记录的，参考深度优先搜索
另外，可能还有一些特别的形状也要事先定义好。这样可以简化编程
找出所有的叶节点，用MSXML可以
记录中间过程的数据，需要仔细斟酌。可以直接记录在结点的属性里，也可以记录在数组里。次序要事先规定好，不然会乱

仅供参考