tree - 如何在图中找到具有最大可能高度的树？

Question

您应该假设给出了常规图。图不是多重图，也没有自边。我正在寻找上限为 O(n^2) 的算法

标签： treegraph-traversal

Answer 1

具有最大高度的树将包括（从根到叶）G 中可能的最长路径。

在未加权、无向图中找到最长路径的问题是 NP-hard。因此，没有 O(n²) 算法来解决它。