我几天前问了一个类似的问题，但我还没有找到解决我的问题的有效方法。 我正在开发一个简单的控制台游戏，我有一个像这样的二维数组：
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个区域分别为:
1
1,1
1
1,1,1,1
1
和：
1
1,1
1
我一直在研究的算法可以找出一个单元格的相邻单元格的所有邻居，并且在这种类型的矩阵上运行得很好。但是，当我使用更大的数组（例如90 * 90）时，程序非常缓慢，有时使用的巨大数组会导致堆栈溢出。
我的另一个问题有人告诉我连接组件标记法是解决我的问题的有效方法。
请问是否有人可以向我展示任何使用此算法的C++代码，因为我对它的工作方式以及这个不相交集数据结构有点困惑...
非常感谢您的帮助和时间。
我将先给你代码，然后稍微解释一下：
// 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);
}
这是解决这个问题的常见方法。
方向向量只是一种找到四个方向上邻居单元格的好方法。
dfs 函数对网格执行深度优先搜索。这意味着它将访问从起始单元格可达的所有单元格。每个单元格都将被标记为current_label。
find_components函数遍历网格的所有单元格，并在发现标记为1的未标记单元格时启动组件标记。
这也可以使用堆栈进行迭代来完成。 如果将堆栈替换为队列，则获得bfs或广度优先搜索。
dfs(x + dx[direction], y + dy[direction], current_label); 中使用了一个512x512网格的整数堆栈，导致溢出。 - Vigneshulimit -s unlimited 然后再运行程序。另一个选项是使用堆栈实现搜索。 - gus这可以通过并查集来解决（虽然正如其他答案所示，DFS可能会更简单一些）。
这个数据结构背后的基本思想是不断地合并同一组中的元素。通过将每个组表示为一棵树（其中节点跟踪其自己的父节点，而不是反过来），您可以通过遍历到根节点来检查两个元素是否在同一组中，并且您可以通过将一个根节点作为另一个根节点的父节点来合并节点。
下面是一个简短的代码示例：
const int w = 5, h = 5;
int input[w][h] = {{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}};
int component[w*h];
void doUnion(int a, int b)
{
// get the root component of a and b, and set the one's parent to the other
while (component[a] != a)
a = component[a];
while (component[b] != b)
b = component[b];
component[b] = a;
}
void unionCoords(int x, int y, int x2, int y2)
{
if (y2 < h && x2 < w && input[x][y] && input[x2][y2])
doUnion(x*h + y, x2*h + y2);
}
int main()
{
for (int i = 0; i < w*h; i++)
component[i] = i;
for (int x = 0; x < w; x++)
for (int y = 0; y < h; y++)
{
unionCoords(x, y, x+1, y);
unionCoords(x, y, x, y+1);
}
// print the array
for (int x = 0; x < w; x++)
{
for (int y = 0; y < h; y++)
{
if (input[x][y] == 0)
{
cout << ' ';
continue;
}
int c = x*h + y;
while (component[c] != c) c = component[c];
cout << (char)('a'+c);
}
cout << "\n";
}
}
演示页面可显示使用不同字母的每组“1”。
p i
pp ii
p i
pppp
p
可以很容易地修改此代码以分别获取组件或获取与每个组件对应的元素列表。一种想法是将上面的 cout << (char)('a'+c); 替换为 componentMap[c].add(Point(x,y))，其中 componentMap 是一个 map<int, list<Point>>，该映射中的每个条目都对应一个组件并给出一个点列表。
有各种优化方法可提高并查集的效率，上述仅是基本实现。
package addressextraction;
public class ConnectedComponentLabelling {
int[] dx={+1, 0, -1, 0};
int[] dy={0, +1, 0, -1};
int row_count=0;
int col_count=0;
int[][] m;
int[][] label;
public ConnectedComponentLabelling(int row_count,int col_count) {
this.row_count=row_count;
this.col_count=col_count;
m=new int[row_count][col_count];
label=new int[row_count][col_count];
}
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]!=0 || m[x][y]!=1) return; // already labeled or not marked with 1 in m
// mark the current cell
label[x][y] = current_label;
// System.out.println("****************************");
// recursively mark the neighbors
int direction = 0;
for (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]==0 && m[i][j]==1) dfs(i, j, ++component);
}
public static void main(String[] args) {
ConnectedComponentLabelling l=new ConnectedComponentLabelling(4,4);
l.m[0][0]=0;
l.m[0][1]=0;
l.m[0][2]=0;
l.m[0][3]=0;
l.m[1][0]=0;
l.m[1][1]=1;
l.m[1][2]=0;
l.m[1][3]=0;
l.m[2][0]=0;
l.m[2][1]=0;
l.m[2][2]=0;
l.m[2][3]=0;
l.m[3][0]=0;
l.m[3][1]=1;
l.m[3][2]=0;
l.m[3][3]=0;
l.find_components();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(l.label[i][j]);
}
System.out.println("");
}
}
}
void CC(unsigned char* pBinImage, unsigned char* pOutImage, int width, int height, int CON8)
{
int i, j, x, y, k, maxIndX, maxIndY, sum, ct, newLabel=1, count, maxVal=0, sumVal=0, maxEQ=10000;
int *eq=NULL, list[4];
int bAdd;
memcpy(pOutImage, pBinImage, width*height*sizeof(unsigned char));
unsigned char* equivalences=(unsigned char*) calloc(sizeof(unsigned char), maxEQ*maxEQ);
// modify labels this should be done with iterators to modify elements
// current column
for(j=0; j<height; j++)
{
// current row
for(i=0; i<width; i++)
{
if(pOutImage[i+j*width]>0)
{
count=0;
// go through blocks
list[0]=0;
list[1]=0;
list[2]=0;
list[3]=0;
if(j>0)
{
if((i>0))
{
if((pOutImage[(i-1)+(j-1)*width]>0) && (CON8 > 0))
list[count++]=pOutImage[(i-1)+(j-1)*width];
}
if(pOutImage[i+(j-1)*width]>0)
{
for(x=0, bAdd=true; x<count; x++)
{
if(pOutImage[i+(j-1)*width]==list[x])
bAdd=false;
}
if(bAdd)
list[count++]=pOutImage[i+(j-1)*width];
}
if(i<width-1)
{
if((pOutImage[(i+1)+(j-1)*width]>0) && (CON8 > 0))
{
for(x=0, bAdd=true; x<count; x++)
{
if(pOutImage[(i+1)+(j-1)*width]==list[x])
bAdd=false;
}
if(bAdd)
list[count++]=pOutImage[(i+1)+(j-1)*width];
}
}
}
if(i>0)
{
if(pOutImage[(i-1)+j*width]>0)
{
for(x=0, bAdd=true; x<count; x++)
{
if(pOutImage[(i-1)+j*width]==list[x])
bAdd=false;
}
if(bAdd)
list[count++]=pOutImage[(i-1)+j*width];
}
}
// has a neighbour label
if(count==0)
pOutImage[i+j*width]=newLabel++;
else
{
pOutImage[i+j*width]=list[0];
if(count>1)
{
// store equivalences in table
for(x=0; x<count; x++)
for(y=0; y<count; y++)
equivalences[list[x]+list[y]*maxEQ]=1;
}
}
}
}
}
// floyd-Warshall algorithm - transitive closure - slow though :-(
for(i=0; i<newLabel; i++)
for(j=0; j<newLabel; j++)
{
if(equivalences[i+j*maxEQ]>0)
{
for(k=0; k<newLabel; k++)
{
equivalences[k+j*maxEQ]= equivalences[k+j*maxEQ] || equivalences[k+i*maxEQ];
}
}
}
eq=(int*) calloc(sizeof(int), newLabel);
for(i=0; i<newLabel; i++)
for(j=0; j<newLabel; j++)
{
if(equivalences[i+j*maxEQ]>0)
{
eq[i]=j;
break;
}
}
free(equivalences);
// label image with equivalents
for(i=0; i<width*height; i++)
{
if(pOutImage[i]>0&&eq[pOutImage[i]]>0)
pOutImage[i]=eq[pOutImage[i]];
}
free(eq);
}
import java.util.ArrayList;
public class cclabeling
{
int neighbourindex;ArrayList<Integer> Temp;
ArrayList<ArrayList<Integer>> cc=new ArrayList<>();
public int[][][] cclabel(boolean[] Main,int w){
/* this method return array of arrays "xycc" each array contains
the x,y coordinates of pixels of one connected component
– Main => binary array of image
– w => width of image */
long start=System.nanoTime();
int len=Main.length;int id=0;
int[] dir={-w-1,-w,-w+1,-1,+1,+w-1,+w,+w+1};
for(int i=0;i<len;i+=1){
if(Main[i]){
Temp=new ArrayList<>();
Temp.add(i);
for(int x=0;x<Temp.size();x+=1){
id=Temp.get(x);
for(int u=0;u<8;u+=1){
neighbourindex=id+dir[u];
if(Main[neighbourindex]){
Temp.add(neighbourindex);
Main[neighbourindex]=false;
}
}
Main[id]=false;
}
cc.add(Temp);
}
}
int[][][] xycc=new int[cc.size()][][];
int x;int y;
for(int i=0;i<cc.size();i+=1){
xycc[i]=new int[cc.get(i).size()][2];
for(int v=0;v<cc.get(i).size();v+=1){
y=Math.round(cc.get(i).get(v)/w);
x=cc.get(i).get(v)-y*w;
xycc[i][v][0]=x;
xycc[i][v][1]=y;
}
}
long end=System.nanoTime();
long time=end-start;
System.out.println("Connected Component Labeling Time =>"+time/1000000+" milliseconds");
System.out.println("Number Of Shapes => "+xycc.length);
return xycc;
}
}