一尘不染

树中的中心节点

algorithm

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


阅读 299

收藏
2020-07-28

共1个答案

一尘不染

继续从树中删除叶节点,直到剩下一个节点为止(如果剩下两个节点,则删除其中一个节点)。该节点最大程度地减少了它与其他每个节点的最大距离。

例:

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

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

2020-07-28