给定2D数组,找到簇

Question

给定2D数组,例如:

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

Answer 2

一种方法是使用图表。以某种顺序遍历矩阵（我会从左到右，从上到下）。当遇到非零元素时，将其添加到图中。然后检查它的所有邻居（看起来您想要 8 个连接的邻居），对于每个非零的邻居，将其节点添加到图中，并将其连接到当前元素。图表中的元素可能必须跟踪它们的坐标，以便您可以查看是否添加了重复项。遍历完矩阵后，您将得到一个包含一组簇的图。簇应该是连接元素的子图。