Number of Islands using BFS
Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such grid, write an algorithm using Breadth-First Search(BFS) to find the number of islands in it.
Example 1: Input: 11110 11010 11000 00000 No of Islands: 1 Example 2: Input: 11000 11000 00100 00011 No of Islands: 3 Example 3: Input: 11110 00010 00010 11110 No of Islands: 1
Earlier have solved a similar problem using DFS – No of Islands using DFS, in this article, we will solve it using Breadth-First Search
Approach: Use Breadth-First Search (BFS)
If all the nodes in the grid are connected then after BFS all the nodes will be visited and there will be only one Island in the grid. If there are more islands in the grid we need to multiple BFS to visit them all. So Number of Islands will be equal to the number of BFS required to visit all isLands (1’s)
- Start the BFS from the node with value 1 and try all four directions (right, left, up and down) to find any connected 1’s.
- Once BFS is completed, check if there is an unvisited node present in the grid (node will have a value 1), if yes then start another BFS from that node. Keep counting no of DFS’s, this will be our answer- Number of Islands.
No of Islands: 1 No of Islands: 3