连接组件标签 [英] Connected Component Labelling

问题描述

我也问过类似的问题，前一些日子，但我还没有找到解决我的问题的有效途径。 我正在开发一个简单的控制台游戏，我有一个二维数组是这样的：

I have asked a similar question some days ago, but I have yet to find an efficient way of solving my problem. I'm developing a simple console game, and I have a 2D array like this:

1,0,0,0,1
1,1,0,1,1
0,1,0,0,1
1,1,1,1,0
0,0,0,1,0

我想找到的所有领域，它由相邻的1的（4路连接）的。所以，在这个例子中，2个区域表现如下：

I am trying to find all the areas that consist of neighboring 1's (4-way connectivity). So, in this example the 2 areas are as following:

1
1,1
  1
1,1,1,1
      1

和

       1
     1,1
       1

这个算法，我一直在努力，找到了小区的邻居所有的邻居和工作完全正常对这种矩阵。然而，当我用更大的阵列（如90 * 90），该程序非常缓慢，有时是用来导致堆栈溢出的巨大阵列。

The algorithm, that I've been working on, finds all the neighbors of the neighbors of a cell and works perfectly fine on this kind of matrices. However, when I use bigger arrays (like 90*90) the program is very slow and sometimes the huge arrays that are used cause stack overflows.

这是我的其他问题有个人告诉我的连接成分标签作为一种有效的解决我的问题。

One guy on my other question told me about connected-component labelling as an efficient solution to my problem.

有人可以告诉我任何C ++ code使用这种算法，因为我有点困惑如何，它实际上与此不相交集数据结构的东西的工作原理以及...

Can somebody show me any C++ code which uses this algorithm, because I'm kinda confused about how it actually works along with this disjoint-set data structure thing...

非常感谢您的帮助和时间。

Thanks a lot for your help and time.

推荐答案

我首先给你code，然后解释了一下：

I'll first give you the code and then explain it a bit:

// direction vectors
const int dx[] = {+1, 0, -1, 0};
const int dy[] = {0, +1, 0, -1};

// matrix dimensions
int row_count;
int col_count;

// the input matrix
int m[MAX][MAX];

// the labels, 0 means unlabeled
int label[MAX][MAX];

void dfs(int x, int y, int current_label) {
  if (x < 0 || x == row_count) return; // out of bounds
  if (y < 0 || y == col_count) return; // out of bounds
  if (label[x][y] || !m[x][y]) return; // already labeled or not marked with 1 in m

  // mark the current cell
  label[x][y] = current_label;

  // recursively mark the neighbors
  for (int direction = 0; direction < 4; ++direction)
    dfs(x + dx[direction], y + dy[direction], current_label);
}

void find_components() {
  int component = 0;
  for (int i = 0; i < row_count; ++i) 
    for (int j = 0; j < col_count; ++j) 
      if (!label[i][j] && m[i][j]) dfs(i, j, ++component);
}

这是解决这个问题的一种常见的方式。

This is a common way of solving this problem.

的方向向量，是一个不错的方式找到相邻小区（每个四个方向）。

The direction vectors are just a nice way to find the neighboring cells (in each of the four directions).

与DFS 函数执行的深度优先搜索的电网。这只是意味着它会访问所有的细胞中的起始细胞到达。每个单元将标有 current_label

The dfs function performs a depth-first-search of the grid. That simply means it will visit all the cells reachable from the starting cell. Each cell will be marked with current_label

在 find_components 功能穿过网格的所有细胞，并启动一个组件标记，如果发现未标记的细胞（标有1）。

The find_components function goes through all the cells of the grid and starts a component labeling if it finds an unlabeled cell (marked with 1).

使用一叠这也可以做反复。 如果你有一个队列替换堆​​栈，你获得的 BFS 或广度优先搜索的。

This can also be done iteratively using a stack. If you replace the stack with a queue, you obtain the bfs or breadth-first-search.

这篇关于连接组件标签的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！