为什么可以用prim算法求半径最小生成树

Prim 算法的本质是一种贪心算法，在每一次选取一个与当前生成树距离最近的节点加入生成树中。因此，Prim 算法得到的生成树一定是以当前根节点为根的最小生成树。

假设我们已经得到了以节点 $u$ 为根节点的最小生成树 $T$，现在需要求以节点 $v$ 为根节点的最小生成树。我们可以将 $u$ 作为初始根节点，运行 Prim 算法得到以 $u$ 为根节点的最小生成树 $T'$，那么 $T'$ 中与 $v$ 相连的边一定是连接 $u$ 和 $v$ 的最短边。

因此，我们可以将 $T$ 中的边与 $T'$ 中连接 $u$ 和 $v$ 的最短边进行比较，选择权值更小的边，得到以节点 $v$ 为根节点的最小生成树 $T''$。显然，$T''$ 也是以节点 $v$ 为根节点的最小生成树。

综上所述，我们可以使用 Prim 算法得到任意两个节点之间的最小生成树。由于树的半径定义为从根到叶子的最大距离，我们可以按照上述方法求出以每个节点为根节点的最小生成树，然后对所有最小生成树求出直径，取最小值即为半径最小的生成树。