请提出了一些算法来找到一棵树，距离最远的节点是最小的所有节点之间的节点 [英] Please suggest some algorithm to find the node in a tree whose distance to its farthest node is minimum among all the nodes

问题描述

请推荐一些算法寻找一棵树的距离最远的节点是最小的所有节点之间的节点。

Please suggest some algorithm to find the node in a tree whose distance to its farthest node is minimum among all the nodes.

它是不是一个曲线图，它是不加权。

Its is not a graph and it is not weighted.

推荐答案

选择任意节点的 v 的树中的 T 的。 运行BFS制作的 v 的作为的 T 的根。 BFS从输出的 v 的距离到所有其他节点的 T 的。

Choose an arbitrary node v in the tree T. Run BFS making v as the root of T. BFS outputs the distances from v to all the other nodes of T.

现在选择一个节点的 U 的最远距离的 v 的。 再次运行BFS制作的 U 的作为根。 在新的远程输出，找到一个节点的是W 的最远距离的 U 的。

Now choose a node u that is farthest from v. Run again BFS making u as the root. On the new distance output, find a node w that is farthest from u.

考虑之间的 U 和是W 的路径。 这是在树的 T 的最长路径。 在路径的midle的节点是中心树的 T 的。

Consider the path between u and w. This is the longest path in the tree T. The node in the midle of the path is the center of the tree T.

请注意，有可能在树中存在两个中心。如果是这样，他们是邻居。

Note that there may exist two centers in a tree. If so, they are neighbours.

性能： O（N）的，其中的 N 的是 T 的

Performance: O(n), where n is the number of nodes of T.

要求：叶（ U 的），它是最远的部分的节点的 v 的在于最长的路径上

Claim: a leaf (u) that is furthest from some node v lies on the longest path.

如果我们证明这一点，则算法是正确的，因为它第一次发现的 U 的，并且，因为它是最长的路径的一端，使用DFS找到这条路本身。

If we prove it, then the algorithm is correct, since it first finds u, and, since it's one end of the longest path, uses DFS to find this path itself.

在索赔证据：让我们用retucto归谬法。假设的 U的第十四部分的是树中最长的路径;而对于一些节点的 v 的既不的 v --- U 的，也不是的 v第十四部分的距离最长路径的 v 。相反，最长路径是 v ---氏/ EM>。我们有两种情况：

Proof of the claim: Let's use retucto ad absurdum. Assume u---r is the longest path in the tree; and for some node v neither v---u, nor v---r is the longest path from v. Instead, the longest path is v---k. We have two cases:

A）的 U的第十四部分和 v - 输出氏/ em>的具有公共节点的 0 的。随后的 v - 输出Ø - U 和 v - 输出Ø - R的的比短的ü - O ---氏/ EM>。随后的 0第十四部分的比的 0 ---氏/ em>的短。随后的ü - O第十四部分的是不是在图中最长的路径，因为ü - O ---氏/ em>的是更长的时间。这违背了我们的假设。

a) u---r and v--k have a common node o. Then v--o--u and v--o--r are shorter than u---o---k. Then o---r is shorter than o---k. Then u---o---r is not the longest path in graph, because u---o---k is longer. It contradicts our assumption.

B）的 U的第十四部分和 v - 输出氏/ em>的不具有公共节点。但由于图是连通的，也有节点的 O1 的和的 o2的的每个的这些路径，使得它们之间的路径的 O1 - O2 的不包含在这两个路径中的任何其他节点。矛盾的假设是相同点），但与 O1 - O2 的，而不是单纯的 0 的（事实上，点的在是一个特例的 B 的，其中的 O1 = O2 的）。

b) u---r and v--k don't have common nodes. But since the graph is connected, there are nodes o1 and o2 on each of these paths, such that the path between them o1--o2 doesn't contain any other nodes on these two paths. The contradiction to the assumption is the same as in point a), but with o1--o2 instead of mere o (in fact, point a is just a special case of b, where o1=o2).

这证明索赔，因此算法的正确性。

This proves the claim and hence the correctness of the algorithm.

（这证明写的帕维尔Shved 和原作者可能有一个较短的）。

(this is proof written by Pavel Shved, and the original author might have a shorter one).

这篇关于请提出了一些算法来找到一棵树，距离最远的节点是最小的所有节点之间的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！