data-structures - 找到不属于树的任何可能直径的边缘

Question

我很好奇是否有一种快速的方法来查找是否存在不属于 n 叉树的任何可能直径的边缘。例如在下面的树中，AB 边不会是任何直径的一部分。

我尝试列出所有可能的直径，但这需要很多时间，而且我确信有更快的方法。

标签： data-structurestreegraph-algorithm

Answer 1

让我们从一个更简单的问题开始：我们如何找到树的任何直径？一种方法是选择某个节点并在该节点处植树。然后可以通过以下两种方式之一找到图形的直径：

1. 直径可能纯粹包含在这些子树之一中。
2. 可以通过取两个子树的根，计算从每个子树根开始的最长路径，然后通过整个树根将它们连接在一起来找到直径。

所以想象一下，我们递归地访问每个子树，并从每个子树中获取从该子树的根开始的最长路径（我们可以通过让每个节点存储其高度来隐式存储它）和纯粹在该子树内的最长路径的长度（可能通过用该树中最长路径的长度标记每个子树来隐式存储）。一旦我们有了这些信息，我们就可以找到如下的直径：直径是

1. 纯粹在这些子树之一内的最长路径，或
2. 通过从子树的根开始通过根连接两条最长的路径而形成。

所有这些信息都可以使用 O(n) 辅助存储在 O(n) 时间内计算出来，因此如果我们只需要确定直径是多少，我们可以相当快地完成。

现在，让我们修改它以实际找到所有可能被使用的边。我们可以从根节点开始。考虑通过路线 (1) 和 (2) 获得的路径的长度。如果路径 (1) 产生的路径比路径 (2) 严格更长，我们可以递归地下降到包含该长度路径的每个子树，并运行相同的过程来识别可能使用的边。如果路由 (2) 产生的路径比路由 (2) 严格更长，那么我们会将从根到其每个子树的边标记为正在使用，这些子树具有从子树根开始的最长路径，并且如果恰好有一个然后，我们会将与第二长路径绑定的每个子树标记为正在使用的子树。然后我们递归地下降到那些子树中，

第二个传播步骤需要时间 O(n)，因为每个节点只被访问一次，并且完成的工作与子节点的数量成正比。总的来说，这是一个使用 O(n) 空间的 O(n) 时间算法。