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

Question

首先，我有一个 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以获取连接的组件。

但是，考虑到这种特殊图的特点，是否有其他快速完成工作的方法？

我会非常感激。

更新：

我已经为此“情况”实现了一个简单的算法here。

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

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

- blackball

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

第二个算法也是线性的，但只有基准测试才能告诉我们它是否真正更快。并查集算法的优势在于它的优化。这将优化延迟到第二步，但完全消除了第一步。

如果您将联合步骤与最近邻计算相结合，然后在第二遍收集集合，可能可以挤出更多的性能。

- John Dvorak

Answer 2

如果您想按顺序执行它，可以使用加权快速联合和路径压缩来执行。复杂度为O（N + Mlog（log（N）））。请查看此链接。 以下是伪代码，以纪念@pycho的话。

`

 public class QuickUnion
    {
    private int[] id;

    public QuickUnion(int N)
    {
         id = new int[N];
         for (int i = 0; i < N; i++) id[i] = i;
    }

    public int root(int i)
    {
         while (i != id[i])
         {
             id[i] = id[id[i]];
             i = id[i];
         }
         return i;
    }

    public boolean find(int p, int q)
    {
        return root(p) == root(q);
    }

    public void unite(int p, int q)
    {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }

    }

如果您想并行查找连接组件，可以使用指针跳转和路径压缩的加权快速联合方法将渐进复杂度降低到O(log(log(N)))时间。请查看此链接。

https://vishwasshanbhog.wordpress.com/2016/05/04/efficient-parallel-algorithm-to-find-the-connected-components-of-the-graphs/

- backcoder

---

非常感谢您与我们分享您的知识。但是，如果您自己编写所有答案而不是提供链接，那将会更好。 - surajs1n

太好了。 :) 保持微笑，愉快编码。 - surajs1n

Answer 3

由于每个节点只有一个出边，因此您可以一次遍历图形中的一个边，直到到达已经访问过的顶点。出度为1意味着在这一点上进行任何进一步的遍历都只会带您到已经到达过的地方。该路径中遍历的顶点都在同一个组件中。

以您的示例为例：

0->1->2->3->2, so [0,1,2,3] is a component
4->2, so update the component to [0,1,2,3,4]
5->6->7->6, so [5,6,7] is a component
8->6, so update the compoent to [5,6,7,8]
9->8, so update the compoent to [5,6,7,8,9]

您可以恰好访问每个节点一次，因此时间复杂度为O(n)。空间复杂度为O(n)，因为您只需要为每个节点提供一个组件ID和组件ID列表。

- AlwaysBTryin

---

事实上，我的例子可能对你的想法来说太特殊了，因为它缺少一种合并操作。O(n) 只是最好情况。 - blackball