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:
-1, -1 |
0, -1 |
1, -1 |
-1, 0 |
0 , 0 |
1, 0 |
-1, 1 |
0, 1 |
1, 1 |
Algorithm
- Set
numberOfIsLands = 0
- Create visitedVertex boolean array
- Iterate rows of graph from 0 to n-1
- Iterate cols of graph from 0 to n-1
- If
graph[row][col] is not visited
then- Set
numberOfIsLands = numberOfIsLands + 1
- Call modified DFS with graph, current row, current column and visitedVertex array
- Set
- If
- Iterate cols of graph from 0 to n-1
return numberOfIsLands
Latest Source Code:
Github: IslandsFinder.java
Output:
Number of Islands are: 5