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

Question

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

谢谢

标签： algorithmdata-structuresgraph-algorithm

Answer 1

不，没有这样的保证。幸运的是，Kruskal's 使用不相交集数据结构来保持到目前为止扫描的边缘的连通性，并且代表对于这个目的并不重要。如果您最终想要树结构，则需要做一些不同的事情（在边集上进行 DFS，为不相交集数据结构子创建一个动态树，以便您可以连接实际的端点，请改用 Prim 的）。