the number of connected component

Question

Compute the number of connected component in a matrix, saying M. Given two items with coordinates [x1, y1] and [x2, y2] in M, M(x1, y1) == -1 && M(x2, y2) == -1 && |x1-x2|+|y1-y2|=1 <=> they are connected

Example:

-1  0 -1  0  0
-1 -1  0 -1 -1
 0  0  0  0 -1
 0  0  0 -1 -1
 0  0  0 -1  0
 0 -1  0  0  0
 0 -1  0  0  0

Output: 4. And they are:

-1
-1 -1

-1

-1 -1
   -1
-1 -1
-1

-1
-1

My idea is to scan the matrix.

Initialization:
count = 0.

For every item in the matrix, do the following three tests.

(1) If it's 0, skip

(2) If it's -1, check its four neighbors. If there is a neighbor whose value is not 0 and -1, assign the value of this neighbor to the current item. Otherwise, count++, ant then assign count to the current item.

(3) If it's not 0 and -1, assign the value of current item to its four neighbors whose value is -1.

The following is my code:

int num_cc(int m[][COLS])
{
    int count = 0; 
    int r;
    int c;

    for(r = 0; r < ROWS; ++r)
    {
        for(c = 0; c < COLS; ++c)
        {
            if(m[r][c] == 0)
                continue;

            if(m[r][c] == -1)
            {
                if(r-1>=0 && m[r-1][c] > 0)
                    m[r][c] = m[r-1][c];
                else if(r+1<ROWS && m[r+1][c] > 0)
                    m[r][c] = m[r+1][c];
                else if(c-1>=0 && m[r][c-1] > 0)
                    m[r][c] = m[r][c-1];
                else if(c+1<COLS && m[r][c+1] > 0)
                    m[r][c] = m[r][c+1];
                else
                {
                    count++;
                    m[r][c] = count;
                }
            }

            if(m[r][c] > 0)
            {
                if(r-1>=0 && m[r-1][c] == -1)
                    m[r-1][c] = m[r][c];
                if(r+1<ROWS && m[r+1][c] == -1)
                    m[r+1][c] = m[r][c];
                if(c-1>=0 && m[r][c-1] == -1)
                    m[r][c-1] = m[r][c];
                if(c+1<COLS && m[r][c+1] == -1)
                    m[r][c+1] = m[r][c];       
            }

        }
    }

    return count;
}

Can anyone help me verify it? Is it correct? Or is there any other solutions?

Thanks,

Answer 1

Style: Depending on coding guidelines and preferences you may want to consider moving the declaration of r and c into the for-loops (for (int r = 0...), as these variables are not supposed to be used outside of the loop, and hence, an outside declaration kind of contradicts this contract.

Correctness: I'm afraid your greedy approach does not work out well - in other words: it gives wrong results. Consider the following matrix (or if you loop the other way round its symmetric variant) :

 0  0  0  0 -1
-1 -1 -1 -1 -1

By going through the first row first, you would create your first connected group with this intermediate result, before the row-loop switches to the second row:

 0  0  0  0  1
-1 -1 -1 -1  1

Next, the inner loop will find another -1 cell with no higher-numbered neighbors and create a second connected component, although there really is only one.

Succinctness: If the code was correct, you might as well eliminate all the if statements in the loop except for the one comparing against -1. The others are redundant in their behavior.

Answer 2

Please check the following link:

http://en.wikipedia.org/wiki/Connected-component_labeling