请建议一些算法来找到树中与其最远节点的距离在所有节点中最小的节点 [英] Please suggest some algorithm to find the node in a tree whose distance to its farthest node is minimum among all the nodes

问题描述

请建议一些算法来找到树中与最远节点的距离在所有节点中最小的节点。

它不是图形，不加权。

解决方案

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

现在选择距离 v 最远的节点 u 。
再次运行BFS，以 u 为根。
在新距离输出中，找到距离 u 最远的节点 w 。

u 和 w 之间的路径。
这是树中最长的路径 T 。
路径中间的节点是 T 树的中心。

注在树中可能存在两个中心。

性能： O（n），其中 是节点的数量

： 距离节点 v 最远的叶（ u ）位于最长的路径上。

如果我们证明它，那么算法是正确的，因为它首先发现 u ，并且，因为它是最长路径的一端，所以使用DFS来寻找这个路径本身。 >

声明的证明：让我们使用retucto ad absurdum。假设 u --- r 是树中的最长路径;对于某些节点 v 既不是 v --- u ，也不是 v --- r 是从。相反，最长路径是 v --- k 。我们有两种情况：

a） u --- r 和 v-k o 。然后， v - o - u 和 v - o - r 短于 u --- o --- k 。然后 o --- r 短于 o --- k 。然后， u --- o --- r 不是图表中最长的路径，因为 u --- o --- k 它与我们的假设矛盾。

b） u --- r 和 v- k 公共节点。但是由于图连接，在这些路径的每一个上都有节点 o1 和 o2 ，使得它们之间的路径 o1-o2 不包含这两个路径上的任何其他节点。与假设的矛盾与点a）相同，但是使用 o1-o2 而不是 o （实际上， >只是 b 的特殊情况，其中 o1 = o2 ）。

（这是由 Pavel撰写的证明Shved ，原作者可能有一个较短的）。

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.

解决方案

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.

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.

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.

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

Proof

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

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.

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---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---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.

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

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