This post is completed by 1 user

  • 0
 Add to List
Medium

427. 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:

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.

Output:

No of Islands: 1
No of Islands: 3

Source: Leetcode

Related Problems: