在1-NN图中查找连通分量的快速方法？

Question

首先,我得到了一个N​​*N距离矩阵,对于每个点,我计算了它的最近邻居,所以我们有一个N*2矩阵,看起来像这样:

0 -> 1  
1 -> 2  
2 -> 3  
3 -> 2  
4 -> 2  
5 -> 6  
6 -> 7  
7 -> 6  
8 -> 6  
9 -> 8

第二列是最近邻居的索引.所以这是一种特殊的有向图,每个顶点都有,只有一个外度.

当然,我们可以先将N*2矩阵转换为标准图形表示,然后执行BFS/DFS以获取连接的组件.

但是,鉴于这个特殊图表的特点,还有其他快速的方法来完成这项工作吗？

我将非常感激.

更新:

我在这里为这种情况 实现了一个简单的算法.

看,我没有使用union-find算法,因为数据结构可能会让事情变得那么容易,我怀疑它是否是我案例中最快的方法(我的意思是实际上).

您可能会认为_merge过程可能很耗时,但如果我们在分配新标签时将边缘交换到连续位置,则合并可能成本很低,但需要另外N个空格来跟踪原始索引.

Answer 1

在给定边列表的情况下查找连通分量的最快算法是并查找算法：对于每个节点，将指针保存到同一集合中的节点，并且所有边都收敛到同一节点，如果您找到长度为至少2，重新向上连接底部节点。

这肯定会在线性时间内运行：

- push all edges into a union-find structure: O(n)
- store each node in its set (the union-find root)
    and update the set of non-empty sets: O(n)
- return the set of non-empty sets (graph components).

由于边列表几乎已经形成并查找树，因此可以跳过第一步：

for each node
- if the node is not marked as collected
-- walk along the edges until you find an order-1 or order-2 loop, 
   collecting nodes en-route
-- reconnect all nodes to the end of the path and consider it a root for the set.
-- store all nodes in the set for the root.
-- update the set of non-empty sets.
-- mark all nodes as collected.
return the set of non-empty sets

第二种算法也是线性的，但只有基准测试才能判断它是否实际上更快。并查算法的优势在于其优化。这将优化延迟到第二步，但完全删除了第一步。

如果您将并集步骤与最近邻计算结合起来，然后在第二遍中收集集合，您可能会获得更多的性能。