Find the number of islands.

Given a boolean 2D matrix, find the number of islands.

This is an variation of the standard problem: “Counting number of connected components in a undirected graph”.

A connected component – connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path(s), and which is connected to no other vertices outside the subgraph.

Solution:
This problem can be solved by DFS

The eight possible moves:

Algorithm

1. Set numberOfIsLands = 0
2. Create visitedVertex boolean array
3. Iterate rows of graph from 0 to n-1
   1. Iterate cols of graph from 0 to n-1
      1. If graph[row][col] is not visited then
         1. Set numberOfIsLands = numberOfIsLands + 1
         2. Call modified DFS with graph, current row, current column and visitedVertex array
4. return numberOfIsLands

Video

Connected Components

Latest Source Code:
Github: IslandsFinder.java

Output:

 Number of Islands are: 5