算法来计算连接元件的数量为在一个矩阵中的每个元素 [英] Algorithm to count the number of connected elements for each element in a matrix

问题描述

我要寻找的方式找到的矩阵连接（相邻的）元件的数量。 我给定一个二维阵列对象，其中每个对象可具有标志集。如果该标志被设置我需要计数具有标志设置藏汉邻居数量。对于每个邻居的处理被重复。

I am looking for way to find the number of connected (neighboring) elements in a matrix. I'm given a 2D-array of objects where each object may have a flag set. If the flag is set I need to count the number of neighbours that have the flag set aswell. For each neighbour the process is repeated.

有关问题的可视化查看图片：

See the image for a visualization of the problem:

我想这是一个相当普遍的问题。什么是它的名字，所以我可以做我自己的研究？

I guess this is a rather common problem. What is it's name so I can do my own research?

推荐答案

这是可以做到的 洪水填充 ，这是 DFS 的变体。这假设你的矩阵实际上是一个曲线图，其中每个小区是一个节点，并且有两个相邻小区之间的边缘。

It can be done with flood fill, which is a variant of DFS. This assume your matrix is actually a graph, where each cell is a node, and there is an edge between two adjacent cells.

一个可能的伪code可能是：

a possible pseudocode could be:

DFS(v,visited):
   if v is not set: 
       return []
   else:
        nodes = [v]
        for each neighbor u of v:
            if u is not in visited:
                  visited.add(u)
                  nodes.addAll(DFS(u,visited))
        return nodes

如果你从某一点 v 启动，它会返回一个包含连接到 v 所有节点（包括T名单 v 本身），你可以轻松地设置自己的价值为尺寸（节点）。

If you start from some point v, it will return t list containing all nodes connected to v (including v itself), and you can easily set their "value" as size(nodes).

下面的伪code将迎来他们的集群的规模所有节点：

The following pseudo code will mark ALL nodes with the size of their "cluster":

markAll(V): //V is the set of all cells in the matrix
    visited = [] //a hash set is probably best here
    while (V is not empty):
       choose random v from V
       visited.add(v)
       nodes = DFS(v,visited)
       for each u in nodes:
            value(u) = size(nodes)
       V = V \ nodes //set substraction

这种方法的复杂性将是 O（| V |）= O（N * M） - 在基体的大小，以便线性（也就是N * M ）

Complexity of this approach will be O(|V|) = O(n*m) - so linear in the size of the matrix (which is n*m)

这篇关于算法来计算连接元件的数量为在一个矩阵中的每个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！