python - マトリックス内の最大連結成分の特定

Question

1´s と 0´s を含む python numpy マトリックスがあります。マトリックス内の 1 の最大の「コレクション」を特定する必要があります: http://imgur.com/4JPZufS

マトリックスには最大 960.000 の要素を含めることができるため、ブルート フォース ソリューションは避けたいと考えています。

この問題を解決するための最も賢明な方法は何ですか?

Answer 1

disjoint-setと呼ばれるデータ構造を使用できます(これは python 実装です)。このデータ構造は、この種のタスクのために設計されました。

現在の要素が 1 の場合、行を反復処理し、既にトラバースされた隣接要素のいずれかが 1 であるかどうかを確認します。そうであれば、この要素をそのセットに追加します。複数のユニオンがある場合、それらのセット。隣人が 1 でない場合は、新しいセットを作成します。最後に最大のセットを出力します。

これは次のように機能します。

def MakeSet(x):
  x.parent = x
  x.rank   = 0
  x.size = 1

def Union(x, y):
  xRoot = Find(x)
  yRoot = Find(y)
  if xRoot.rank > yRoot.rank:
    yRoot.parent = xRoot
  elif xRoot.rank < yRoot.rank:
    xRoot.parent = yRoot
  elif xRoot != yRoot: # Unless x and y are already in same set, merge them
    yRoot.parent = xRoot
    xRoot.rank = xRoot.rank + 1
  x.size += y.size
  y.size = x.size

def Find(x):
  if x.parent == x:
    return x
  else:
    x.parent = Find(x.parent)
    return x.parent

""""""""""""""""""""""""""""""""""""""""""

class Node:
  def __init__ (self, label):
    self.label = label
  def __str__(self):
    return self.label

rows = [[1, 0, 0], [1, 1, 0], [1, 0, 0]]
setDict = {}
for i, row in enumerate(rows):
  for j, val in enumerate(row):
    if row[j] == 0:
      continue
    node = Node((i, j))
    MakeSet(node)
    if i > 0:
      if rows[i-1][j] == 1:
        disjointSet = setDict[(i-1, j)]
        Union(disjointSet, node)
    if j > 0:
      if row[j-1] == 1:
      disjointSet = setDict[(i, j-1)]
      Union(disjointSet, node)
    setDict[(i, j)] = node
print max([l.size for l in setDict.values()])

>> 4

これは、上記のリンクから取得した素集合のコードを使用した完全な動作例です。