複雑さの少ない配列で同様の要素をグループ化するにはどうすればよいですか？

Question

は、我々はこのような矩形配列の整数値を有すると仮定する：

A = [[1,1,2,2,2], 
    [1,2,2,2,1], 
    [1,3,3,3,1]] 

どのグループ異なるクラスタに互いに接続されている同一の整数値か？クラスタのサイズはが不明ですです。同じことをするのに最も適したアルゴリズムである

Group 1 : A[0,0],A[0,1],A[1,0],A[2,0] 
Group 2 : A[0,2],A[0,3],A[0,4],A[1,1],A[1,2],A[1,3] 
Group 3 : A[1,4],A[2,4] 
Group 4 : A[2,1],A[2,2],A[2,3] 

：

必要な出力（相互に接続されているのと同じ整数の異なるクラスタ）。 この問題に対して機械学習を使用できますか？

Answer 1

任意のグラフ検索アルゴリズム（BFSまたはDFS）が行います。

グラフの頂点はマトリックスの要素であり、隣接する要素間にはエッジが存在するため、各頂点は2〜4個の隣接を持ちます。

各要素のクラスタ数と、まだクラスタに属していない要素の他の値（たとえば-1）を格納する同じサイズの補助行列を作成します。 ここで、クラスタを取得するには、行列のすべての要素をループします。 まだクラスタに属していない要素を見つけたら、そこからBFSまたはDFSを実行して、接続された等しい値のコンポーネントを見つけ、補助行列のこれらの値をすべて新しいクラスタの番号でマークします。

複雑さはO（要素数）です。行列を読み書きするのと同じです。