gpt4 book ai didi

algorithm - 树中最长路径的公共(public)段

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:25:39 26 4
gpt4 key购买 nike

我遇到了一道编程题,其中一个是

  1. 给定一棵加权树。
  2. 一个人感兴趣的节点集合,我们称这个集合为 S。

我们需要返回最长的理想路径的最短公共(public)段。理想路径是在属于上述集合 S 的顶点上开始和终止的路径。不能保证公共(public)路径存在。我知道在线性时间内找到树中最长的路径,我们也可以很容易地将它扩展到理想路径的情况,但是 2 dfs 的经典算法不会帮助找到最长的路径,但只是最长的路径长度。谢谢。

最佳答案

如果你有:

  1. 路径开始
  2. 路径长度,从 DFS 或 BFS 等算法中得到
  3. 路径结束

您可以轻松获取路径。更改代码:

//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
}

关于algorithm - 树中最长路径的公共(public)段,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15274106/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com