如何将矩阵分解为连通分量的和？

Question

我有一个由0和1组成的矩阵：

       1 0 0 0 0
       0 0 1 1 0
  a =  0 0 1 1 0
       1 0 0 0 0
       1 1 0 0 0

我想用Python把它分解成一些连通的部分。这里的“连通”是指每个“1”周围至少有一个其他的“1”在上面、下面、左边或右边。如果没有这样的“1”，那这个“1”就算是孤立的：

       1 0 0 0 0   1 0 0 0 0   0 0 0 0 0   0 0 0 0 0
       0 0 1 1 0   0 0 0 0 0   0 0 1 1 0   0 0 0 0 0
  a =  0 0 1 1 0 = 0 0 0 0 0 + 0 0 1 1 0 + 0 0 0 0 0
       1 0 0 0 0   0 0 0 0 0   0 0 0 0 0   1 0 0 0 0
       1 1 0 0 0   0 0 0 0 0   0 0 0 0 0   1 1 0 0 0

有趣的是，在这个问题中（二维二进制矩阵中最大的1的矩形），Guy Adini建议使用广度优先搜索（BFS）来将矩阵分解成连通部分。不过我找不到用Python实现这个方法的代码，也不知道怎么用BFS来解决我的问题。

Answer 1

这里有一个自定义的实现方式。如果你想的话，可以修改它来去掉重复的部分。

import itertools

class Matrix():
    def __init__(self, matrix):
        self.matrix = matrix

    def computeConnectedComponents(self):
        rows_id = list(range(len(self.matrix)))
        cols_id = list(range(len(self.matrix[0])))

        #here are the position of every 1 in the grid. ( row number, column number) indexes start at 0
        positions = [couple for couple in self.generate_pairs(rows_id, cols_id) if self.matrix[couple[0]][couple[1]]==1]

        #here we store all the connected component finded
        allConnectedComponents = []

        #while there is position not affected to any connected component
        while positions != [] :
            #the first element is taken as start of the connected component
            to_explore = [positions.pop(0)]
            currentConnectedComponent = set()
            #while there is node connected to a node connected to the component
            while list(to_explore) != []:
                currentNode = to_explore.pop()
                currentConnectedComponent.add(currentNode)

                to_explore += [coord for coord in self.node_neighbourhood(currentNode) if (self.matrix[coord[0]][coord[1]]==1 and (coord not in to_explore) and (coord not in currentConnectedComponent))]

                allConnectedComponents.append(currentConnectedComponent)
                positions = [position for position in positions if position not in currentConnectedComponent]

        return allConnectedComponents

    #http://stackoverflow.com/questions/16135833/generate-combinations-of-elements-from-multiple-lists
    def generate_pairs(self, *args):
        for i, l in enumerate(args, 1):
            for x, y in itertools.product(l, itertools.chain(*args[i:])):
                yield (x, y)

    def node_neighbourhood(self, coordinates):
        row, column = coordinates[0], coordinates[1]
        result = []
        if (row - 1) >= 0 :
            result.append((row-1, column))
        if (row + 1) < len(self.matrix):
            result.append((row+1, column))
        if (column - 1) >= 0:
            result.append((row, column-1))
        if (column + 1) < len(self.matrix[0]):
            result.append((row, column+1))
        return result


if __name__ == "__main__":
    data = [[1,0,0,0,0],
           [0,0,1,1,0],
           [0,0,1,1,0],
           [1,0,0,0,0],
           [1,1,0,0,0]]

    matrix = Matrix(data)
    for connectedComponent in matrix.computeConnectedComponents():
        print(connectedComponent)

Answer 2

一个可行的算法如下：

• 你需要保持一个和原始矩阵大小一样的 visited 矩阵，用来记录哪些元素已经被算法访问过（或者说，你可以用一个集合来存储这些被访问元素的坐标）。

• 然后，你要逐个检查矩阵中的所有元素：

  • 如果某个元素没有被访问过，并且它的值是1，你就把它标记为已访问，然后递归地探索它周围的所有邻居。这个递归的函数需要返回所有连接的元素（可以是一个包含这些元素的矩阵，或者是一个包含它们坐标的集合等等）。