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

标签 algorithm minimum-spanning-tree kruskals-algorithm

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

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

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

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

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

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

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

最佳答案

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

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

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

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

关于algorithm - Kruskal 最小生成树中的交叉点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47133889/

相关文章:

python - 使用邻接表表示最小生成树

algorithm - Floyd-Warshall 算法 - 为什么这个顺序?

algorithm - 旅行商最小生成树变体

algorithm - 在线性时间内查找最小生成树是否包含边?

python - Boruvka算法并行实现CUDA

algorithm - 使用 Kruskal 算法找到图中的最小割点?

c# - 用c#画形状

algorithm - 是否有一条边可以在不断开图形的情况下删除?

algorithm - 双向 key 加密/哈希算法

python - 不使用 SET 的两个字符串列表之间的区别