6

まず、N * N距離行列を取得しました。各ポイントについて、最近傍を計算したので、N*2行列が作成されました。次のようになります。 

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

2番目の列は、最近傍のインデックスでした。したがって、これは特別な種類の有向グラフであり、各頂点には1つの次数しかありませんでした。

もちろん、最初にN * 2行列を標準のグラフ表現に変換し、BFS/DFSを実行して連結成分を取得することもできます。

しかし、この特別なグラフの特徴を考えると、仕事をするための他の速い方法はありますか？

本当にありがたいです。

アップデート：

ここでは、この場合 の簡単なアルゴリズムを実装しました。

ほら、私はユニオン検索アルゴリズムを使用しませんでした。データ構造によって物事がそれほど簡単ではなくなる可能性があるためです。私の場合、それが最速の方法であるかどうかは疑問です（私は実際に意味しました）。

_mergeプロセスには時間がかかる可能性があると主張することもできますが、新しいラベルを割り当てながらエッジを連続した場所に入れ替えると、マージにかかる費用はほとんどかかりませんが、元のインデックスをトレースするにはさらにN個のスペースが必要です。

4

3 に答える 3

5

エッジリストを指定して連結成分を検索するための最速のアルゴリズムは、ユニオン検索アルゴリズムです。各ノードについて、同じセット内のノードへのポインターを保持し、次の長さのパスを見つけた場合は、すべてのエッジを同じノードに収束させます。少なくとも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

2番目のアルゴリズムも線形ですが、実際に高速かどうかを判断できるのはベンチマークだけです。union-findアルゴリズムの強みは、その最適化です。これにより、最適化が2番目のステップに遅れますが、最初のステップは完全に削除されます。

最近傍計算を使用してユニオンステップに参加し、2番目のパスでセットを収集すると、おそらくもう少しパフォーマンスを引き出すことができます。

于 2012-11-02T07:57:33.653 に答える
1

各ノードには出力エッジが1つしかないため、既にアクセスした頂点に到達するまで、一度に1つのエッジだけグラフをトラバースできます。アウトディグリー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]

各ノードに1回だけアクセスできるため、時間はO（n）です。必要なのは各ノードのコンポーネントIDとコンポーネントIDのリストだけなので、スペースはO（n）です。

于 2012-11-02T17:48:33.390 に答える
1

順次実行したい場合は、加重クイックユニオンとパス圧縮を使用して実行できます。複雑さ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;
    }

    }

`@reference https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

連結成分を並列に見つけたい場合は、ポインタージャンプとパス圧縮を使用した加重クイックユニオンを使用して、漸近的複雑さをO（log（log（N））時間に減らすことができます。このリンクを確認してください

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

于 2016-05-04T18:01:57.360 に答える