我有一个MST，需要删除一个节点。我知道有一个O(log^4(n))的算法，但由于MST包含不到50个节点和2500条边，而且我已经对边进行了排序，我想用一个更基本的解决方案。我为每个连接的组件创建一个联合体，然后在他们身上运行Kruskal来重新连接。
我的推理是，这应该是可行的，因为我们有一个MST，在删除一个节点后，通过最便宜的方式重新连接。
然而，我没有找到任何东西来确认这个工作，所以我想在这里仔细检查一下。
在剩余的节点和边缘中，生成的树是最小的跨接树吗？
它工作得很好，但它没有O(log^4(n))那么快。
它的工作原理很容易证明：使用 Kruskal 算法，如果一条边的端点没有任何路径连接，只有廉价的较早的边，那么这条边就会被选中。
删除一个顶点和它的边缘并不会创建任何新的路径（它只是删除了路径），所以如果你再次运行整个算法，任何之前被选中的边缘仍然会被选中。