树中心节点

Question

给定一棵树,如何在树中找到中心节点,使得从中心节点到其他节点的距离最小(假设每条边具有单位重量)？我正在尝试使用DFS但是可以在线性时间内完成吗？

Answer 1

继续从树中删除叶节点,直到留下单个节点(如果留下两个节点,则删除其中任何一个节点).该节点最小化从其到每个其他节点的最大距离.

例:

   *                 *              
  / \                 \
 *   *                 *              *
      \                 \              \
       *      =>         *     =>       *    =>   *
        \                 \                     
         *                 *
          \
           *

要在线性时间内实现此功能,请将所有初始叶节点插入FIFO队列中.对于每个节点,还要存储其子节点的数量.从队列中删除元素时,请减少其父元素的子元素数.如果此数字变为零,则将父项插入队列.

Answer 2

这是另一种也在运行的方法O(V).

选择v1树上的任何顶点.从此顶点运行BFS.v2你将要进行的最后一个顶点()将是最远的顶点v1.现在运行另一个BFS,这次是从顶点开始v2并获取最后一个顶点v3.

从路径v2到v3是树的直径和你的心就在它的地方.更准确地说,它位于它的中间.如果路径2n + 1有点,则只有1个中心(在该位置n + 1).如果路径2n点,都会有在位置上的两个中心n和n + 1.

您只能使用2个2 * O(V)及时运行的BFS调用.