Algorithm to count the number of connected elements for each element in a matrix

Question

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?

Answer 1

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.

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

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).

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

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

Answer 2

How about utilizing the Disjoint set or union-find data structure?

Basically:

Whenever a flag is added, or you notice that an element has a flag, scan that element's neighbours. As soon as you find an element therein with a flag, you cluster the elements together by having them point to the same parent element. Either directly or recursively.

Keep a tally of the element count for every cluster.