algorithm - 如何检查给定的生成树是否为 MST？

Question

假设我们有一个图 G 和它的生成树 T。我们如何检查此生成树是否是 MST？

我建议对于不在 T 中的每条边 i，所有边 j 都在 T< 的唯一路径上 从 i 的一端到另一端，我们必须有 w_i >= w_j

Answer 1

你要检查对于每条不在 MST 中的边 (u, v)，在 MST 中从 u 到 v 的路径中没有权重大于 (u, v) 的边。对于树中的单个顶点，您可以使用单个 BFS 或 DFS 找到通往所有其他节点的路径上的最大权重边，因此这给出了 O(n²) 算法(n次 O(n) 搜索)。如果不从头开始对每个顶点进行操作，您可能会做得更好。也就是说，只计算 MST 并查看所有边权重的总和是否相同可能更有效。正如@Niklas 在评论中提到的，有用于验证 MST 的线性时间方法，但它们似乎涉及更多。