我在寻找一种算法,通过边缘加权树找到最长的路径。这个图是无圈的和连通的,但是没有有向,只有稀疏连接的,没有定义的起点,可以有很多叶节点。最长的路径只能穿过一条边缘并通过一个顶点一次。
一种简化的表示法,如本例所示,其中边权值与长度成正比。

会有B-C-D-G-H-I。
我看过标准的图遍历算法,例如BFS、DFS、MST等,但似乎都不适合我的问题。
在我去实现一个蛮力算法之前,我想我会在这里检查任何建议的解决方案。
发布于 2022-10-21 15:38:31
请注意,所有最长的路径都必须在一个叶节点(一个只有一个链接的节点)开始和结束。
因此,您可以通过只查看对叶节点来优化搜索。
发布于 2022-10-27 03:22:42
在图论中,无圈连通图被称为树。
若要在无向边缘加权树中查找最长路径,请执行以下操作:
选择任何顶点,u
u选择最长的路径--说它在v
v到最长的路径--说它在w结束
从v到w找到的路径是树中最长的路径。对于步骤2和步骤3,我认为没有理由选择BFS与DFS。
运行时间: BFS和DFS是O({##**$$}}*),但由于这是一棵树,我们知道比顶点少一个边,所以我们的总运行时间降到了O(νV_x)。
https://stackoverflow.com/questions/74149954
复制相似问题