最小直径生成树算法
给定一个无向连通图G，找到一棵直径最小的生成树。
Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
给定一个无向连通图G，找到一棵直径最小的生成树。
Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum.
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（1）
singhsumit 链接了 Hassin 和 Tamir 的相关论文，题为“论最小直径生成树问题”，但他的答案目前已被删除。论文的主要思想是，在无向图中找到最小直径生成树可以通过找到图的“绝对 1 中心”并返回以该处为根的最短路径树来完成。
绝对 1 中心是顶点或边上的点，从该点到最远顶点的距离最小。这可以通过 Kariv 和 Hakimi 的算法（网络位置问题的算法方法。I：p 中心）或 Hakimi、Schmeichel 和 Pierce 的早期算法（论网络中的 p 中心）找到，我将尝试仅根据运行时间和数十年的事后诸葛亮来重建。 （愚蠢的付费墙。）
使用弗洛伊德-沃歇尔或约翰逊的算法来计算所有对的距离。对于每条边 u--v，找到该边上 1 中心的最佳候选，如下所示。
让边 u--v 上的点由 µ 索引，范围从 0（u 本身）到 len(u--v)（v 本身）。从索引 µ 处的点到顶点 w 的距离为
作为 µ 的函数，该量先增加后减少，最大值为
按此 argmax 对顶点进行排序。对于将数组分为左子数组和右子数组的每个分区，计算产生相同 argmax 分区的 µ 区间 [a, b]。将此区间与[0, len(u--v)]相交；如果路口是空的，则继续前进。否则，求左子数组中距 u--v 上由 a 索引的点的最大距离 L，以及右子数组中距 u--v 上由 b 索引的点的最大距离 R。 （通过在开始时从左到右和从右到左扫描，计算这些最大值的成本可以为每个分区分摊到 O(1)。）最好的选择是 [a, b] 中的 µ最小化 max(L - (µ - a), R + (b - µ))。
singhsumit linked the relevant paper by Hassin and Tamir, entitled "On the minimum diameter spanning tree problem", but his answer is currently deleted. The main idea from the paper is that finding a minimum diameter spanning tree in an undirected graph can be accomplished by finding the "absolute 1-center" of the graph and returning a shortest path tree rooted there.
The absolute 1-center is the point, either on a vertex or an edge, from which the distance to the furthest vertex is minimum. This can be found via an algorithm of Kariv and Hakimi (An Algorithmic Approach to Network Location Problems. I: the p-Centers) or an earlier algorithm of Hakimi, Schmeichel, and Pierce (On p-Centers in Networks), which I will attempt to reconstruct from just the running time and decades of hindsight. (Stupid pay walls.)
Use Floyd--Warshall or Johnson's algorithm to compute all-pairs distances. For each edge u--v, find the best candidate for a 1-center on that edge as follows.
Let the points on the edge u--v be indexed by µ ranging from 0 (u itself) to len(u--v) (v itself). The distance from the point at index µ to a vertex w is
As a function of µ, this quantity is increasing and then decreasing, with the maximum at
Sort the vertices by this argmax. For each partition of the array into a left subarray and a right subarray, compute the interval [a, b] of µ that induce the same argmax partition. Intersect this interval to [0, len(u--v)]; if the intersection is empty, then move on. Otherwise, find the maximum distance L in the left subarray from the point on u--v indexed by a, and the maximum distance R in the right subarray from the point on u--v indexed by b. (The cost of computing these maximums can be amortized to O(1) for each partition, by scanning left-to-right and right-to-left at the beginning.) The best choice is the µ in [a, b] that minimizes max(L - (µ - a), R + (b - µ)).