我发现最小生成树 (MST) 的某些边使用联合查找方法重叠,详见 here ,经过修改 - 使用 float
而不是 integer
权重,使用 integer
值而不是 string
ID。下图中的灰线是 MST 边缘,绿色/蓝色边缘是形状边界。
边成本是节点之间的欧氏距离。
不是节点 87 -> 138(权重 = 17.7)和 55 -> 134(权重 = 9.49),它不应该是 55 -> 138 和 87 -> 134 吗?是实现错误还是算法本身会发生这种情况?
除了顶点数(它们是连接到每个节点的边的组合权重),请忽略括号中的数字。
附言我发现 55 -> 138 和 87 -> 134 之间的距离完全相同 (12.20656)。
最佳答案
根据 AakashM 提出的问题回答我自己的问题。
具体来说,这是因为 55 -> 138 和 87 -> 134 之间的边成本完全相同。这发生在我的例子中,因为我使用图像生成形状,因此点之间的距离被量化。
受此启发,我向边缘添加了非常小的随机权重(小于像素之间的最小距离)(编辑:没有)解决了这个问题!
因此,该算法仍然适用于欧氏 MST,我的具体实现包含一个警告。
关于algorithm - Kruskal 最小生成树中的交叉点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47133889/