我一直在尝试解决以下问题(请注意，这不是家庭作业，我只是使用过去几年课程的作业练习考试(：https://i.stack.imgur.com/Q2OtS.png。
我希望有人验证或改进我完成这项任务的方法，因为我不确定是否有更快的方法(或者我所做的是否正确，真的(。
我的解决方案：
1(首先，我计算每个望远镜之间的距离(使用勾股定理(，给我一个O(V^2(复杂度过程，但考虑到V的最大值是300，它并没有那么糟糕。我使用这些加权边构建了一个完整的图形。
2(接下来，我使用Kruskal的算法找到这个图的最小生成树，以O(E log(V((的复杂度运行。
(这是我不确定的地方(
3(由于这是一个树形图，我可以找到它的中心，忽略边缘权重。
4(一旦我找到了中心(考虑到单顶点中心，还没有考虑如何处理两个顶点中心(，我将这个图划分为子图(一个与从中心出来的每条边相关的子图(
5(对于每个顶点，我计算其与中心的距离(考虑权重(-O(E(复杂度
6(对于每个子图，取两个距中心最大距离的顶点 - 大约O(V log(V((复杂度
7(取以这种方式获得的所有顶点对，然后再次从中取最大两个顶点。如果它们不在同一个子图中，我们就完成了，并将这两者与新的边缘连接起来。
8(如果它们在同一个子图中，请转到3(，并在子图上递归运行。
我的问题是 - 这是我可以实现的最快的解决方案吗？更重要的是，它是否正确？谢谢。
不幸的是，您的算法不会产生正确的答案。
请考虑您提供的练习表屏幕截图上的第一个示例。那里有 7 个顶点，让我们按照给出的顺序从 1 到 7 对它们进行编号。我同意望远镜网络最初是一个最小生成树，因为描述中说明了"所有电缆的总长度都是最小的"。
以下边缘是我计算出的此 MST 的边缘(使用顶点上的建议编号(：
{1,3}, {2,3}, {3,4}, {4,5}, {4,6}, {6,7}
使用您查找中心的方式，中心是顶点 4，因为其他每个顶点最多距离它 2 跳。现在，让我们按照您的建议将 MST 划分为其子图。有 3 个子图(我使用它们的顶点集来识别它们(：
- {1,2,3}
- {5}
- {6,7}
因此，离中心最远的顶点是
{2,5,7}
Cleary，从顶点 2 到顶点 7 的距离最高。我使用勾股定理计算出 9.99 = sqrt(10( + 2 + sqrt(8( + 2 的距离。如您所建议的，您的解决方案是连接顶点 2 和顶点 7 以最小化直径。
但是有一个更好的解决方案：连接顶点 3 和顶点 7(如练习中给出的解决方案(。原因是从顶点 1 到顶点 7 的距离从 9.06 = sqrt(5( + 2 + sqrt(8( + 2 下降到 8.82 = sqrt(10( + sqrt(32(。使用您的解决方案，从顶点 1 到顶点 7 的最小距离仍为 9.06，这无法实现最佳效果。
其次，不需要您在步骤 8 中建议的递归。它是一棵树，那么三个子图中的一个怎么会在不通向中心的路线上连接到另一个子图呢？如果是，图形将包含一个循环，因为子图已经通过中心连接。
第三，在密集图上，最好将 Prim-Dijkstra 用于实现 O(E + Vlog(v(( 的 MST。它非常容易实现，例如您可以在维基百科上查找它。我想你已经知道了。
最后，如何产生正确的结果？
如您所见，如何使用启发式方法找到边缘并不明显，因为您的想法没有实现。
什么是幼稚的解决方案？您几乎可以选择每个顶点对，即 O(n^2( 许多候选边。要计算其直径(天真地(，您需要 O(n^2(。因此，您可以尝试每条边，并在插入此附加边的情况下计算树的直径。最后，输出最小直径。这将是 O(n^2 * n^2( = O(n^4(。
我们怎样才能做得更好？我喜欢先考虑天真的解决方案，因为你知道你需要看什么东西。从那里你开始删除不必要的操作。您正确发现的是最长路径需要变短(否则直径不会改变(。换句话说，您添加的边必须连接位于最长路径上的两个折点。但是你不知道是哪两个。您可以轻松构建每个顶点都是最长路径的一部分的示例，但对于分布良好的望远镜网络，最长路径上的顶点要少得多。现在，您只需尝试沿最长路径插入边，并在 O(n^2( 中再次计算新直径。如果在最长路径上有 k 个顶点，则得到 O(n^2 k^2(。
总结：
- 在完整图上使用 Prim 算法 -> O(n^2( 计算生成树
- 计算树的最长路径，即直径 -> O(n^2( 以获得最长路径上的所有 k 个顶点
- 尝试在此最长路径上的所有顶点对之间一次添加一条 (O(k^2( 条(条边，并存储所有直径的最小值，即您必须一次又一次地重新计算直径 (O(n^2((。总计： O(n^2 k^2(
如果我们能改进计算直径的时间，那就太好了。对于树，这适用于线性时间，请参阅查找树直径的线性算法。你的图最初是一棵树，但后来你一次最多添加一个边，即它几乎仍然是一棵树。所以你需要做的就是找到原始树中最远的两个节点 u1、v1，然后在我们的算法中插入边 e={u，v} 时，你删除了与顶点 u 处的 e 不同的边，这样循环就消失了，你又有了一棵树。现在，您再次找到最远的顶点 u2、v2。现在，您计算四个顶点 u1、u2、v1、v2 之间的最大距离，这是线性时间的直径。
这将缩短运行时间到 O(n*k^2 + n^2(