Algorithm to find the total number of connected se

问题:

i wanted to know which algorithm should i apply here. Would a DFS do?

Given a 2–d matrix. Find the total number of connected sets in that matrix.

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions (i.e. N, W, E, S, NE, NW, SE, SW direction). A cell is not a neighbor of itself.

For example:

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

number of connected sets is 3

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

number of connected set is 9.

回答1:

I don't think you will need to think of it as a general graph problem and apply any algorithm such as BFS or DFS.

You will need to do three scans of the matrix.

scan 1:

start from the top

1. give every number each 1 with 1..n, in you example the first row would after that step would look like

   1 0 0 2

2. go to the next line and for every 1 in the row check if the neighbor to your left is non-0
   • if non-0 take on the value to the left
   • if 0 check for non-0 neighbors in the previous line and take on the value of the left most one
   • if all of those are 0 that simply add 1 to the maximum number given so far
3. repeat 2 until last line has been processed

and your example should look like follows

1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2

scan 2:

start from the bottom check if each neighbor has the same number as the left most neighbor as well as the same number as the neighbor in the row below it

basically if you have a matrix like this

1 0 2

1 0 2

0 1 0

to check ensure that a set has really the same number

scan 3:

count the number of unique non-0 entries in the matrix

回答2:

Connected-component labeling algorithm is intended to mark out connected groups of elements (both for 4-connectivity and for 8-connectivity)

回答3:

You want to use a disjoint set datastructure and algorithm. This will pick a unique representative for each connected component, which you can count at the end.

To efficiently evaluate which elements are neighbors, you can scan the matrix line by line, maintaining a list of segments (of consecutive 1's) from the previous line, while determining which segments on the current line are adjacent to them.

回答4:

There are 3 connected sets. All 1 which are neighbors of each other are considered as one single set. All 1 at a[1,4], a[2,3], a[3,3] and a[4,4] form one set and one at a[1,1] form one set and one at a[4,1] forms one set.

回答5:

Pythonic Implementation, More understandable code:

# sea is 2 D array of 0 and 1s we have to find 1's group surrounded by 0's
def dfs(sea, i, j, b, h, visited):
    surround = ((-1, -1), (0, -1), (1, -1),
                (-1, 0), (1, 0),
                (-1, 1), (0, 1), (1, 1)
                )
    if can_visit(sea, i, j, b, h, visited):
        for s in surround:
            visited[(i, j)] = 1
            dfs(sea, i + s[0], j + s[1], b, h, visited)


def can_visit(sea, i, j, b, h, visited):
    if i >= 0 and j >= 0 and i < b and j < h:
        if (i, j) not in visited and sea[i][j] == 1:
            return True


def find_island(sea):
    visited = {}
    h = len(sea)
    count = 0
    for i, row in enumerate(sea):
        b = len(row)
        for j, item in enumerate(row):
            if can_visit(sea, i, j, b, h, visited):
                count += 1
                dfs(sea, i, j, b, h, visited)
    return count


sea = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]
       ]

print find_island(sea)

回答6:

Scan the matrix for 1s. When you find one, call a recursive function that marks off its connected component if it is not already identified as being in one. Use recursion to find connected components. Have a quick lookup somewhere that tells you whether a given node has already been identified as being in a connected component to avoid identifying connected components 2x, and to avoid infinite loops while traversing a connected component.

回答7:

If you want do it just by your matrix (without extra memory), do it as follow:

Set scanner position as [0,0]

1. Set a counter to zero.
2. Scan matrix from current scanner position row by row (and cell by cell) and find one 1 and set scanner position to next element after this 1, if there isn't any 1 go to step 6.
3. Set related one to counter+2 and recursively find all of its 1 neighbors and also set them to count + 2.
4. count = count + 1
5. Go to step 2.
6. output count.

PS: It's clear if the scanner position is greater than matrix size your algorithm will finishes (I didn't wrote this to prevent confusion).

回答8:

This isn't nearly as hard as it looks. In fact, this feels very strongly like something a professor would assign for an assignment in first year Computer Science. So if this is homework, you should tag it as such.

However, the solution is fairly easy.

for (int y = 0; y < arr.height(); y++)
{
   for (int x = 0; x < arr.width(); x++)
   {
      if (arr[x][y] == 1)
      {
         if (CheckIfConnected(x, y, arr))
         {
            connectedPositionsX.Add(x);
            connectedPositionsY.Add(y);
         }
      }
   }
}

Where connectedPositions would be a linked list or whatever you want to store sets with.

arr is a 2D array containing a matrix of the type you specified above.

CheckIfConnected can be implemented fairly simply as well.

bool CheckIfConnected(int x, int y, int[][]arr)
    {
       if (arr.width() >= 2) || (arr.height() >= 2)
       {
          if ((x < arr.width()) && (x >= 0) && (y < arr.height()) && (y >= 0))
          {
            if ((x-1) >= 0) //West
            {
                if (arr[x-1][y] == 1)
                {
                    adjCount[x-1][y] += 1;
                    return true;
                }
            }
            if (((x-1) >= 0) && ((y-1) >= 0)) //Northwest
            {
                if (arr[x-1][y-1] == 1)
                {
                    adjCount[x-1][y-1] += 1;
                    return true;
                }
            }
            if ((y-1) >= 0) //North
            {
                if (arr[x][y-1] == 1)
                {
                    adjCount[x][y-1] += 1;
                    return true;
                }
            }
            if (((x+1) < arr.width()) && ((y-1) >= 0)) //Northeast
            {
                if (arr[x+1][y-1] == 1)
                {
                    adjCount[x+1][y-1] += 1;
                    return true;
                }
            }
            if ((x+1) < arr.width()) //East
            {
                if (arr[x+1][y] == 1)
                {
                    adjCount[x+1][y] += 1;
                    return true;
                }
            }

            //I'll let you implement Southeast to Southwest on your own,
            //the pattern is clear now.
          }
       }
       return false;
    }

From there, you know how many times you found a pairing on each position in the grid. This helps you keep track of your connections.

The counts in the 2D array adjCount keeps track of this for you.

You could also go through and modify Dijkstra's Algorithm to do it recursively for you. Since you mentioned DFS (Depth First Search) I'm assuming your professor or teacher wants you to go about solving it that way.

In that case:

Here is Dijkstra's Algorithm in Pseudo Code: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Hope that helps! Cheers!

回答9:

Just keep searching in East, SouthEast, South and SouthWest direction at one go recursively for each node having value as 1. If the call to visit function is a fresh call and not from recursion increase the connected components.

import java.util.Scanner;

public class Solution {

    public static void visit(int[][] ar, boolean[][] v,int i, int j){
        int size = ar.length;
        if(ar[i][j] == 1){
            v[i][j] = true;
            if(j>0 && i<size-1){
                visit(ar,v,i+1,j-1); // SouthWest
            }
            if(i<size-1){
                visit(ar,v,i+1,j); // South
                if(j < size-1)
                    visit(ar,v,i+1,j+1); // SouthEast
            }
            if(j<size-1)
                visit(ar,v,i,j+1); // East
        }
    }

    public static void main(String[] args) {
        int[][] ar;
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ar = new int[n][n];
        boolean[][] v = new boolean[n][n];
        for(int i=0; i<n ; i++) {
            for(int j=0; j<n; j++){
                ar[i][j] = sc.nextInt();
                v[i][j] = false;
            }
        }

        for(int i=0; i<n ; i++) {
            for(int j=0; j<n; j++){                
                if(ar[i][j] == 1 && !v[i][j]){
                    count++;
                    visit(ar,v,i,j);
                }
            }
        }
        System.out.println(count);
    }
}

回答10:

I have a class to help you find the total number of connected components in your 2D array. My class not only gives you the total number, but also gives you the clusters and visualize them for you. You can comment out the parts that you don't need. Please see this class in (java): https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/ConnectedComponetns.java

回答11:

For python try:

import numpy
from scipy import ndimage

data = [[0, 0, 1, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 1],
        [0, 0, 1, 0, 0, 1, 0, 1],
        [0, 1, 0, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 1, 1, 0],
        [1, 0, 1, 1, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

label, index = ndimage.label(data, numpy.ones((3, 3)))

print(label, index)

[[0 0 1 0 0 2 0 0]
 [3 0 0 0 0 0 0 4]
 [0 0 5 0 0 6 0 4]
 [0 5 0 0 0 6 0 0]
 [5 0 0 0 0 0 0 0]
 [0 0 7 7 0 8 8 0]
 [9 0 7 7 0 8 8 0]
 [0 0 0 0 0 0 0 0]] 9