Given a 2D array of numbers, find clusters

Question

Given a 2D array, for example:

0 0 0 0 0
0 2 3 0 1
0 8 5 0 7
7 0 0 0 4

Output should be groups of clusters:

Cluster 1: <2,3,8,5,7>

Cluster 2: <1,7,4>

Answer 1

Your problem seems to be finding connected components. You should use a traverse method (either BFS or DFS will do the work). Iterate over all elements, for each non-zero element start a traverse and record all elements you see in that traverse and turn each visited element into zero. Something like the code below:

void DFS(int x, int y)
{
  printf("%d ", g[x][y]);
  g[x][y] = 0;
  // iterate over neighbours
  for(dx=-1; dx<=1; dx++)
    for(dy=-1; dy<=1; dy++)
      if (g[x+dx][y+dy]) DFS(x+dx, y+dy);
}

for(i=0; i<n; i++)
  for(j=0; j<n; j++)
    if (g[i][j])
    {
      DFS(i, j);
      printf("\n");
    }