San*_*eep 5 c++ algorithm data-structures
请建议一些算法来查找树中的节点,该节点与所有节点之间的最远节点的距离最小.
它不是图表,也没有加权.
Sla*_*ava 10
在树T中选择任意节点v.运行BFS使v成为T的根.BFS输出从v到T的所有其他节点的距离.
现在选择距离v最远的节点u.再次运行BFS使你成为root.在新的距离输出上,找到距离u最远的节点w.
考虑u和w之间的路径.这是树T中最长的路径.路径中间的节点是树T 的中心.
请注意,树中可能存在两个中心.如果是这样,他们就是邻居.
性能:O(n),其中n是T的节点数.
声明:距离某个节点v最远的叶子(u)位于最长的路径上.
如果我们证明它,那么算法是正确的,因为它首先找到你,并且,因为它是最长路径的一端,所以使用DFS来找到这条路径本身.
该证明要求:让我们用retucto归谬法.假设u --- r是树中最长的路径; 而对于一些节点v既不v ---ü,也不v第十四部分是从最长的路径v.相反,最长的路径是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(事实上,a点只是b的一个特例,其中o1 = o2).
这证明了索赔,因此证明了算法的正确性.
(这是Pavel Shved写的证明,原作者可能会更短).
您可以依次在每个节点上使用 Dijkstra 算法（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm），找到从该节点到每个其他节点的所有距离；扫描结果列表以获取到最远节点的距离。一旦你对每个节点进行了 Dijkstra 扫描，另一次扫描将为你提供最大距离的最小值。
Dijkstra 通常被认为具有运行时间O(v^2)，其中 v 是节点数；O(v^3)您将在每个节点运行一次，这会增加简单实现的时间。您可以通过存储早期节点 Dijkstra 运行的结果并在以后的运行中将它们用作已知值来获得收益。