小编Ily*_*iev的帖子

语境

我正在尝试使用 CUDA 实现 Boruvka MST 算法，但根本不需要了解该算法来帮助我。

问题

那么，让我描述一下问题：我有一个图，以边列表格式存储（边数组，每条边用 2 个相邻的顶点 ID 及其权重表示）。

但是，（这非常重要！）为了优化对设备内存的访问，我不是将边存储为单个结构数组，而是存储为三个单独的数组：

• int *src_ids
• int *dst_ids
• 浮动*权重

要访问单边，只需使用该数组的相同索引进行迭代即可：

• src_ids[i]
• 目标 ID[i]
• 权重[i]

现在，当我描述了数据格式后，问题就来了

我想从这三个数组中删除元素（边缘），条件如下：

1)如果 src_id[i] == dst_id[i], 则移除第 i 条边

2）如果 src_id[i] != dst_id[i]，但存在另一条边 j 具有相同的 src_id[j] 和 dst_id[j]，但权重[j]较小，则删除第 i 条边

换句话说，我想：

• 去除边缘
• 连接相同的顶点
• 并复制非最小边

第一个很简单：我可以使用 Throw::remove_if 或按照此处所述进行扫描，从数组中并行删除元素，以删除具有相同 id 的边缘。（我已经通过扫描实现了第二种变体）。

但我未能实现第二部分，即删除重复的边缘。我有一个想法，但不确定这种方法是否有效。让我描述一下。

首先，我们将按以下方式重新排序（或排序）这三个数组：

• 首先按第一个 (src_id) ID 对边进行排序。
• 然后按第二个 (dst_id) id 对第一个 ID 相等的边进行排序。
• 最后，根据权重对两个 id 相等的边进行排序。

当所有边都以这种方式排序时，删除重复的非最小边相对容易：

• 我们只看前一条边 (i-1)，
• 如果它具有相同的 id，但权重较小，则标记当前边缘以进行删除。
• 然后我们只需要应用扫描，类似于 (1 src_id[i] …