树中的中心节点 [英] centre node in a tree

问题描述

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

Given a tree, how to find the centre node in the tree so that the distance from the central node to other nodes is minimum(assuming each edge has unit weight)? I am trying to use DFS but is it possible to do it in linear time?

推荐答案

不断从树中删除叶节点，直到只剩下一个节点(如果剩下两个节点，请删除其中任何一个).该节点最小化了它到每个其他节点的最大距离.

Keep removing leaf nodes from your tree until you are left with a single node (if left with two nodes, remove any one of them). That node minimizes the maximum distance from it to every other node.

示例:

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

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

To implement this in linear time, insert all initial leaf nodes in a FIFO queue. For each node, also store the number of its children. When removing an element from your queue, decrease its parent's number of children. If this number becomes zero, insert the parent into the queue.

这篇关于树中的中心节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！