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

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

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

第二列是最近邻居的索引。所以这是一种特殊的导演 图，每个顶点都有且只有一个出度。

当然，我们可以先将N*2矩阵转换为标准的图表示，然后进行BFS/DFS以获得连通分量。

但是，考虑到这个特殊图的特点，还有其他快速的方法来完成这项工作吗？

我将非常感激。

Update:

我为此实现了一个简单的算法case here https://gist.github.com/4002163.

看，我没有使用并查找算法，因为数据结构可能会让事情变得不那么容易，我怀疑这是否是我的情况下最快的方法（我的意思是实际上）。

你可能会说 _merge 过程可能很耗时，但如果我们在分配新标签时将边交换到连续位置，合并的成本可能很小，但需要另外 N 个空间来跟踪原始索引。

在给定边列表的情况下查找连通分量的最快算法是联合查找 http://en.wikipedia.org/wiki/Disjoint-set_data_structure算法：对于每个节点，持有指向同一集合中的节点的指针，所有边都收敛到同一个节点，如果找到长度至少为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

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

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