algorithm - Kruskal 最小生成树中的交叉点

Question

我发现最小生成树 (MST) 的某些边使用联合查找方法重叠，详见 here ，经过修改 - 使用 float 而不是 integer 权重，使用 integer 值而不是 string ID。下图中的灰线是 MST 边缘，绿色/蓝色边缘是形状边界。

边成本是节点之间的欧氏距离。

显示顶点 ID 的示例。下面添加边权重:

不是节点 87 -> 138(权重 = 17.7)和 55 -> 134(权重 = 9.49)，它不应该是 55 -> 138 和 87 -> 134 吗？是实现错误还是算法本身会发生这种情况？

除了顶点数(它们是连接到每个节点的边的组合权重)，请忽略括号中的数字。

同一示例，缩小以显示其他边权重(删除顶点编号以消除困惑):

附言我发现 55 -> 138 和 87 -> 134 之间的距离完全相同 (12.20656)。

Answer 1

根据 AakashM 提出的问题回答我自己的问题。

具体来说，这是因为 55 -> 138 和 87 -> 134 之间的边成本完全相同。这发生在我的例子中，因为我使用图像生成形状，因此点之间的距离被量化。

受此启发，我向边缘添加了非常小的随机权重(小于像素之间的最小距离)(编辑:没有)解决了这个问题!

因此，该算法仍然适用于欧氏 MST，我的具体实现包含一个警告。