寻找树的中心

本文介绍了寻找树的中心的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个问题，这是我计划的一部分.

I have a question which is part of my program.

对于树 T=(V,E)，我们需要找到树中的节点 v，该节点使从 v 到任何其他节点的最长路径的长度最小.

For a tree T=(V,E) we need to find the node v in the tree that minimize the length of the longest path from v to any other node.

那么我们如何找到树的中心呢?是否可以只有一个或多个中心?

so how we find the center of the tree? Is there can be only one center or more?

如果有人能给我很好的算法，这样我就可以了解如何适应我的程序.

If anyone can give me good algorithm for this so i can get the idea on how i can fit into my program.

推荐答案

有两种方法可以做到这一点(两者同时运行):

There are two approaches to do this (both runs in the same time):

• 使用 BFS(我将在这里描述)
• 使用FIFO队列.

选择树上的任何顶点 v1.从此顶点运行 BFS.您将进行的最后一个顶点 (v2) 将是距离 v1 最远的顶点.现在运行另一个 BFS，这次是从顶点 v2 获取最后一个顶点 v3.

Select any vertex v1 on your tree. Run BFS from this vertex. The last vertex (v2) you will proceed will be the furthest vertex from v1. Now run another BFS, this time from vertex v2 and get the last vertex v3.

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

The path from v2 to v3 is the diameter of the tree and your center lies somewhere on it. More precisely it lies in the middle of it. If the path has 2n + 1 points, there will be only 1 center (in the position n + 1). If the path has 2n points, there will be two centers at the positions n and n + 1.

你只使用了在 2 * O(V) 时间内运行的 2 个 BFS 调用.

You only use 2 BFS calls which runs in 2 * O(V) time.