Number of Islands BFS and DFS in DSA C - Execution Trace

Concept Flow - Number of Islands BFS and DFS

Start: Grid with 0s and 1s

↓

Scan each cell

↓

Is cell == '1' and not visited?

No→Move to next cell

Yes↓

Increment island count

↓

Run BFS or DFS from this cell

↓

Mark all connected '1's as visited

↓

Continue scanning grid

↓

End: Return island count

Scan the grid cell by cell; when a land cell ('1') not visited is found, start BFS or DFS to mark all connected land cells visited, then continue scanning.

Execution Sample

DSA C

void dfs(int r, int c) {
  if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0' || visited[r][c]) return;
  visited[r][c] = true;
  dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
}

int numIslands() {
  int count = 0;
  for (int i=0; i<rows; i++)
    for (int j=0; j<cols; j++)
      if (grid[i][j] == '1' && !visited[i][j]) {
        count++;
        dfs(i, j);
      }
  return count;
}

This code counts islands by scanning the grid and using DFS to mark connected land cells.

Execution Table

Step	Operation	Current Cell	Visited Cells	Island Count	Visual Grid State
1	Start scanning	None	{}	0	[['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
2	Found land cell unvisited	(0,0)	{(0,0)}	1	[['V','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
3	DFS visit neighbors	(0,1)	{(0,0),(0,1)}	1	[['V','V','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
4	DFS visit neighbors	(1,0)	{(0,0),(0,1),(1,0)}	1	[['V','V','0','0','0'], ['V','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
5	DFS visit neighbors	(1,1)	{(0,0),(0,1),(1,0),(1,1)}	1	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
6	Continue scanning	(0,2)	{(0,0),(0,1),(1,0),(1,1)}	1	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1']]
7	Found land cell unvisited	(2,2)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','1','1']]
8	DFS visit neighbors	(2,2)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','1','1']]
9	Continue scanning	(3,3)	{(0,0),(0,1),(1,0),(1,1),(2,2)}	2	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','1','1']]
10	Found land cell unvisited	(3,3)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3)}	3	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','1']]
11	DFS visit neighbors	(3,4)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	3	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','V']]
12	Continue scanning	(3,4)	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	3	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','V']]
13	End scanning	None	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	3	[['V','V','0','0','0'], ['V','V','0','0','0'], ['0','0','V','0','0'], ['0','0','0','V','V']]

💡 All cells scanned; all islands counted and visited.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 11	Final
Island Count	0	1	1	2	3	3
Visited Cells	{}	{(0,0)}	{(0,0),(0,1),(1,0),(1,1)}	{(0,0),(0,1),(1,0),(1,1),(2,2)}	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}	{(0,0),(0,1),(1,0),(1,1),(2,2),(3,3),(3,4)}

Key Moments - 3 Insights

Why do we mark cells as visited during DFS/BFS?

Marking cells as visited prevents revisiting the same land cell multiple times, avoiding infinite loops and double counting islands. See steps 2-5 in execution_table where visited cells grow.

Why do we only start DFS/BFS when we find a '1' cell not visited?

Because only unvisited land cells represent new islands. If visited or water ('0'), we skip. This is shown in step 2 and step 7 where new islands start.

How does DFS/BFS ensure all connected land cells are counted as one island?

DFS/BFS explores all neighbors recursively or iteratively, marking connected land cells visited. This groups connected '1's as one island, as seen from steps 2 to 5 and 10 to 11.

Visual Quiz - 3 Questions

Look at the execution_table, what is the island count after step 7?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Island Count' column at step 7 in execution_table.

At which step does the DFS mark the cell (1,1) as visited?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look at the 'Current Cell' and 'Visited Cells' columns in execution_table rows 3-6.

If the grid had no '1's, how would the island count change in variable_tracker?

A It would increase to 1

B It would remain 0 throughout

C It would increase to the number of cells

D It would be undefined

💡 Hint

Refer to the 'Island Count' variable in variable_tracker starting value and logic in concept_flow.

Concept Snapshot

Number of Islands counts connected groups of '1's in a grid.
Scan each cell; if '1' and unvisited, increment count and run DFS/BFS.
DFS/BFS marks all connected land cells visited.
Result is total islands found.
Key: mark visited to avoid recounting.
Works for 4-directional adjacency.

Full Transcript

The Number of Islands problem scans a grid of '1's and '0's to count how many groups of connected '1's exist. We scan each cell. When we find a '1' that is not visited, we increase the island count and run DFS or BFS from that cell. This search visits all connected land cells, marking them visited to avoid counting them again. We continue scanning until all cells are checked. The final count is the number of islands. The execution table shows each step, which cells are visited, and how the island count grows. The variable tracker follows island count and visited cells. Key points include marking visited cells to prevent infinite loops and only starting searches on unvisited land cells. This method works by exploring neighbors up, down, left, and right.