algorithm - 给定一个二维数组，找到簇

Question

给定一个二维数组，例如:

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

输出应该是集群组:

集群 1:<2,3,8,5,7>

集群 2:<1,7,4>

Answer 1

您的问题似乎是寻找连通分量。您应该使用遍历方法(BFS 或 DFS 都可以)。遍历所有元素，对于每个非零元素开始遍历并记录您在该遍历中看到的所有元素，并将每个访问的元素变为零。类似于下面的代码:

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");
    }