树的发现中心 [英] Finding Center of The Tree

问题描述

我有一个问题属于我的程序。

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?

如果有人可以为此提供好的算法，那么我就可以了解如何适应我的程序。 / p>

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队列。

• using BFS (which I will describe here)
• using FIFO queue.

选择任意顶点 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个BFS调用，它们以 2 * O（V）时间。

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

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