首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >通过无向边缘加权树查找最长路径

问通过无向边缘加权树查找最长路径
EN

Stack Overflow用户
提问于 2022-10-21 07:09:48
回答 2查看 79关注 0票数 0

我在寻找一种算法,通过边缘加权树找到最长的路径。这个图是无圈的和连通的,但是没有有向,只有稀疏连接的,没有定义的起点,可以有很多叶节点。最长的路径只能穿过一条边缘并通过一个顶点一次。

一种简化的表示法,如本例所示,其中边权值与长度成正比。

​

​

会有B-C-D-G-H-I。

我看过标准的图遍历算法,例如BFS、DFS、MST等,但似乎都不适合我的问题。

在我去实现一个蛮力算法之前,我想我会在这里检查任何建议的解决方案。

EN

回答 2

Stack Overflow用户

发布于 2022-10-21 15:38:31

请注意,所有最长的路径都必须在一个叶节点(一个只有一个链接的节点)开始和结束。

因此,您可以通过只查看对叶节点来优化搜索。

票数 0
EN

Stack Overflow用户

发布于 2022-10-27 03:22:42

在图论中,无圈连通图被称为树。

若要在无向边缘加权树中查找最长路径,请执行以下操作:

选择任何顶点,u

  • Find从u选择最长的路径--说它在v

  • Find结束,从v到最长的路径--说它在w

结束

从v到w找到的路径是树中最长的路径。对于步骤2和步骤3,我认为没有理由选择BFS与DFS。

运行时间: BFS和DFS是O({##**$$}}*),但由于这是一棵树,我们知道比顶点少一个边,所以我们的总运行时间降到了O(νV_x)。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/74149954

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档