Count connected dots in a grid

Question

I have a grid of m X n cells. Some of them are on and off state. Find an efficient algorithm to count the no of connections.

Many dots connected in top, left, right, bottom still be considered 1 connection.

Answer 1

Scan your grid in some order. When you reach a cell that is on, perform a flood fill on it.

"Fill" each cell by turning it off. After your flood fill is done, continue your scan.

The number of connected components in the original grid equals the number of times you performed a flood fill.

Answer 2

You can use Depth-first search algorithm. This algorithm could find number of connected components in any undirected graph in time O(E) where E is the number of edges in the graph. On the grid you have O(nm) edges since every vertex has at most four neighbours.

Answer 3

Of course, the good data-structure for this sort of problem ("determine the number of connected components") is the UnionFind data structure; it yields a nearly linear (in the size of the grid) algorithm. But it turns out that for your specific problem, which is reminiscent of maze exercises posed in recreational programming challenges, there is a more primitive, even better (linear) solution.

(My apologies Tom, as I assume this is what you were going for. But flood filling is such a generic technique that I figured this could bear some detailing!)

You color each connected area with a different color. The idea is that to do this, you only need to keep track of how you colored the last processed line of the grid. The trick is to know (a) what color to pick and (b) how to count the different connected areas.

def countConnectedAreas(grid, n):
  vector = [0] * n    # Buffer vector containing current zones.
  count = 0           # Current number of connected areas.
  nextToken = 1       # Next color to use to paint a newly encountered zone.

  for line in grid:
    current = 0
    for i in range(n):
      if not line[i]:
        # Not dot.
        current = 0
      else:
        # There is a dot.
        if current != 0 and vector[i] != 0 and current != vector[i]:
          # This is the tricky case: it means you can paint the next
          # square with two colors, which means that two connected
          # areas are merging. Automatically, this means that you are
          # seeing one less connected area.
          count -= 1
        else:
          current = max(current, vector[i])
          if current == 0:
            # If the neighboring squares are colored 0, then pick a new
            # color.
            current = nextToken
            nextToken += 1
            count += 1

      vector[i] = current

  return count

Here are a couple grids to try this out on:

gridOne = [
  [ True, True, False, False, False, False, True ],
  [ True, True, False, False, False, False, True ],
  [ True, True, False, True, True, False, True ],
  [ True, True, False, False, True, False, True ],
  [ True, True, False, False, False, False, True ],
  [ False, True, False, False, False, False, True ],
  [ False, True, True, False, False, False, True ],
  [ True, False, True, False, False, False, True ] ]

gridTwo = gridOne + [
  [ True, True, True, True, True, True, True] ]

countConnectedAreas(gridOne, 7)    # returns 4
countConnectedAreas(gridTwo, 7)    # returns 2