Number of Islands or Clusters

Given a 2D matrix of 0s and 1s, find total number of clusters formed by elements with value 1.

The algorithm to find total number of clusters of elements with value 1 in a given 2D matrix treats the given matrix as a graph and then it finds out total number of connected components in that graph.

While modeling the 'matrix' as a graph -
1. An element matrix[i][j] with value 1 is considered as a vertex.
2. All adjacent elements of matrix[i][j] with value 1 are considered as its neighbor vertices. An element can have maximum of eight neighbors.

With this graph modeling in place, we use following algorithm to find total number of clusters -
1. Initialize count to 0. Initialize a 2D 'visited' array of booleans which is of size equal to given matrix. Initialize all elements of 'visited' array to false.

2. For an element matrix[i][j], if matrix[i][j] is '1' and visited[i][j] is 'false' then
2a. Increment count by 1.
2b. Start depth first search from element matrix[i][j]. Along with element matrix[i][j], this depth first search would mark all the vertices which are directly or indirectly connected to element matrix[i][j] as visited. In short all the vertices in the cluster starting from vertex matrix[i][j] are visited in this depth first search.

3. Repeat step #2 for all the elements of given 2D matrix.

4. Return the 'count' which is basically total number of clusters of 1s in given 2D matrix.

Time complexity of this algorithm is O(n) where is 'n' is total number of elements in the given 2D array. This algorithm uses O(n) extra space to keep track of visited vertices.
Web post with code visualization: http://www.ideserve.co.in/learn/number-of-clusters-of-1s

Website: http://www.ideserve.co.in

Facebook: https://www.facebook.com/IDeserve.co.in

Видео Number of Islands or Clusters канала IDeserve