我遇到了一个编程问题
- 给定一棵加权树。
- 一个感兴趣的节点集合,我们称这个集合为 S。
我们需要返回最长的理想路径中最短的公共段。理想路径是在属于上述集合 S 的顶点上开始和终止的路径。不能保证公共路径存在。我知道在线性时间内找到树中最长的路径,我们也可以轻松地将其扩展到理想路径的情况,但是 2 dfs 的经典算法无助于找到最长的路径,而只是最长的路径长度。谢谢你。
如果你有:
您可以轻松获得路径。更改代码:
//current vertex is v, next is u, current length is l
u.length = l + 1;
u.visited = true;
cont.push(u);
添加行:
u.previous = v;
然后你可以通过以下方式找到路径:
v = path_end;
while(v != path_begin){
//mark, v belongs to "path"
v = v.previous
}