时间戳

首页 > 解决方案 > 什么算法可以找到无根非二叉树的直径？

computer-science - 什么算法可以找到无根非二叉树的直径？

问题描述

给定一棵无向无根非二叉树，我们必须在尽可能短的运行时间内找到所述树的直径之一，而无需使用递归方法。

我已经看到了许多不同的答案，并且想弄清楚哪个是正确的。当给定一个无向无根非二叉树时，你能否在任何顶点 A 上运行 BFS 以获得最远的顶点 B，然后在 B 节点上运行 BFS，这将导致 B 和结果 C 之间的直径？

除此之外，如果这确实是正确的，那么时间复杂度是多少？我见过 O(E) 和 O(E+V)

标签： computer-sciencegraph-theory

解决方案

我已经看到了许多不同的答案，并且想弄清楚哪个是正确的。当给定一个无向无根非二叉树时，你能否在任何顶点 A 上运行 BFS 以获得最远的顶点 B，然后在 B 节点上运行 BFS，这将导致 B 和结果 C 之间的直径？

是的，这个算法是正确的，d(B, C)那么就是树的直径。您可以在这篇文章中找到有关此算法（及其工作原理）的更多信息。

除此之外，如果这确实是正确的，那么时间复杂度是多少？我见过 O(E) 和 O(E+V)

您在树上运行 BFS 两次。每个 BFS 都有一个时间复杂度，O(V)因为每个顶点只被访问一次。
在树中，E = V-1总是验证相等性，因此对于在树上运行的任何算法，O(V) = O(E) = O(E + V)，所以两种表示法都是正确的。O(V)为了简单明了，恕我直言。

推荐阅读