Sta*_*uff 4 algorithm graph-theory
我被问到一个令我难过的任务.我可能只是想得太多......问题如下.
给出线性时间算法以确定非循环无向图(即树)中最长的未加权路径.
我的第一个目的是使用DFS.但似乎DFS只会给我从我开始的节点到另一个顶点的最长路径; 但是,问题要求树中最长的路径...不是从我开始的节点开始的最长路径.有人会让我直截了当吗？
谢谢.
一种这样的方法是选择任何节点A,并且以线性时间计算到所有其他节点的距离.假设B距离A最远.在步骤2中,找到距离B最远的节点.
设d(P,Q)表示从P到Q的距离.注意,如果E是A,B,C的最低共同祖先,则d(A,B)= d(A,E)+ d(E,B) )并且还注意到,d(E,B)≥d(E,C).
编辑1:算法或方法 - 找到距离任何A最远的B; 找到距离B最远的C; 声称d(B,C)在图中的所有顶点对上都是最大的 - 似乎是合理的,但上面并没有证明它.
一方面,它不一定是d(E,B)≥d(E,C),而另一方面,单独就不足以建立d(B,C)≥d(F,G) F,G是树中的任何节点....