Kruskal的MST :使用Union-Find DS的Union操作:保证在具有最小边权重的节点之间进行连接

Question

在最小生成树中，我们需要在移动到其他边之前连接具有最小权重的边。为了执行连接，我们使用UF DS的联合操作，它连接不相交数据集的代表元素。是否可以保证代表性元素将是我们打算加入的具有最小边权重的节点？连接很可能发生在要连接的组件的其他节点上，如果我没有记错的话。

谢谢

Answer 1

不，没有这样的保证。幸运的是，Kruskal使用不相交集合数据结构来维护到目前为止扫描的边缘的连通性，代表并不重要。如果您最终想要树结构，您需要做一些不同的事情(DFS在边集上，为不相交集数据结构细分一个动态树，以便您可以连接实际的端点，而使用Prim)。