How to detect connected components in a 2D array?

Question

As mentioned the title above. I want to find out whether there are how many components in a 2D Array. Whereas, components are made by 1 numbers and there are only 0 and 1 number in the array. I implemented this problem by using DFS (Deep First Search) algorithm with recursive calls and an array to mark cell visited. However, I want to implement this problem with another way without using recursion, stack, queue, struct... Only using for/while function are allowed.

Example: Array data:

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 1
0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1
0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1
0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1
0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1
0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1
0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0
0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0
0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0
0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0

Array after determined components with specific labels.

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 2 2 2 0 3 3 0 1 0 0 0 0 0 1
0 0 2 0 2 0 3 3 0 1 0 4 4 4 0 1
0 0 2 0 2 0 0 0 0 1 0 4 0 4 0 1
0 0 2 0 2 0 0 0 0 1 0 4 0 4 0 1
0 0 2 2 2 0 0 0 0 1 0 4 0 4 0 1
0 0 0 0 0 5 5 5 0 1 0 4 4 4 0 1
0 0 0 0 0 5 0 5 0 1 0 0 0 0 0 1
0 0 0 0 0 5 5 5 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 6 6 6 6 6 0 0 0 0 7 7 7 7 0 0
0 6 0 0 0 6 0 0 0 0 7 0 0 7 0 0
0 6 0 6 6 6 6 6 0 0 7 7 7 7 0 0
0 6 0 6 0 6 0 6 0 0 7 7 7 7 0 0
0 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0
0 6 6 6 6 6 6 6 0 0 0 0 0 0 0 0

Thank you in advance.

It will be better if you share why you would do this, and what you have tried so far. — herohuyongtao
– herohuyongtao, Commented Mar 3, 2014 at 15:12
Actually, this is my homework and I just stated programing recently. My teacher doesn't allow me to use something that is beyond lesson in my class. That's why I used recursive function in DFS algorithm for this problem but it is not accepted. Using stack, queue, structure are also not allowed. I only can use for/while loop, normal function for this problem. Hope you can sympathize! — Long Uni
– Long Uni, Commented Mar 3, 2014 at 15:17

QQQ · Accepted Answer · 2014-03-04 03:37:15Z

0

I guess you could iterate through the matrix, and check the neighbours for each cell, and copy the value of the neighbour if that is > 0 or set a new value if all the neighbours are 0. In pseudocode:

comp = 1
for i = 0 to n:
  for j = 0 to n:
    for nei : neighbours(i, j):
      if nei > 0:
        m[i,j] = nei
        break
      m[i,j] = comp
      comp++

And neighbours are the 4 (or 2) adjacent neighbouring cells to (i, j)

answered Mar 4, 2014 at 3:37

QQQ

412 silver badges6 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to detect connected components in a 2D array?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related