algorithm - 创建具有深度优先搜索的 MST？

Question

我有一个对称图，并创建了一棵树，其中包含从随机顶点到任何其他顶点的所有最短路径。我可以使用树来构造最小生成树（MST）吗？我的算法类似于深度优先算法。

Answer 1

在最坏的情况下，最短路径树无助于找到最小生成树。考虑一个我们想要找到 MST 的图表。将具有相同大长度边的源顶点添加到其他顶点。来自该源的最短路径树由非常长的边组成，我们先验地知道，因此最短路径树在这种情况下没有用。