在树上中心节点 [英] 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屋！