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.

Practice

1. What does the "Number of Islands" problem ask you to find in a grid of '1's and '0's?

easy

A. Find the longest path of '1's in the grid

B. Count how many groups of connected '1's (islands) are in the grid

C. Calculate the total number of '0's in the grid

D. Replace all '1's with '0's in the grid

Solution

1. Step 1: Understand the problem definition

   The problem asks to find how many separate groups of connected '1's exist in the grid. Each group is called an island.

2. Step 2: Identify what is counted

   We count each cluster of adjacent '1's (connected horizontally or vertically) as one island.

3. Final Answer:

   Count how many groups of connected '1's (islands) are in the grid -> Option B

4. Quick Check:

   Number of islands = count of connected '1' groups [OK]

Hint: Islands = groups of connected '1's in grid [OK]

Common Mistakes:

• Counting individual '1's instead of groups
• Including diagonal connections as connected
• Counting '0's instead of '1's

2. Which of the following is the correct way to start a DFS function to explore neighbors in a grid for the Number of Islands problem in C?

easy

A. int dfs(int row, int col, char* grid)

B. int dfs(char grid[][], int row, int col)

C. void dfs(int row, int col, int grid[][])

D. void dfs(int row, int col, char** grid, int rows, int cols)

Solution

1. Step 1: Check parameter types for grid and indices

   The grid is a 2D array of characters, passed as char** grid. Row and col are integers. Rows and cols are needed to check boundaries.

2. Step 2: Verify function signature matches common DFS pattern

   void dfs(int row, int col, char** grid, int rows, int cols) correctly uses void return type (no return needed), takes row, col, grid pointer, and grid size parameters.

3. Final Answer:

   void dfs(int row, int col, char** grid, int rows, int cols) -> Option D

4. Quick Check:

   Correct DFS signature includes grid pointer and size [OK]

Hint: DFS needs grid pointer, indices, and grid size [OK]

Common Mistakes:

• Using incorrect grid parameter type
• Missing grid size parameters
• Wrong return type for DFS

3. Given the grid:

char* grid[] = {"11000", "11000", "00100", "00011"};
int rows = 4, cols = 5;

What is the number of islands found by a correct BFS or DFS solution?

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Visualize the grid and connected '1's

   Grid rows:
   Row 0: 1 1 0 0 0
   Row 1: 1 1 0 0 0
   Row 2: 0 0 1 0 0
   Row 3: 0 0 0 1 1
   Islands are groups of connected '1's horizontally or vertically.

2. Step 2: Count islands by grouping connected '1's

   Island 1: Top-left block (positions (0,0),(0,1),(1,0),(1,1))
   Island 2: Middle single '1' at (2,2)
   Island 3: Bottom-right block (positions (3,3),(3,4))
   Total islands = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count connected '1' groups = 3 [OK]

Hint: Count connected '1' clusters visually [OK]

Common Mistakes:

• Counting diagonal '1's as connected
• Missing isolated single '1's
• Misreading grid rows or columns

4. In the following DFS code snippet for Number of Islands, what is the bug?

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

medium

A. It does not check for visited cells, causing infinite recursion

B. It modifies the grid, which is not allowed

C. It correctly marks visited cells by setting '1' to '0', no bug

D. It misses diagonal neighbors in DFS

Solution

1. Step 1: Analyze how visited cells are handled

   The code sets grid[r][c] = '0' to mark visited cells, preventing revisiting.

2. Step 2: Check if this approach is valid and complete

   Marking visited by changing '1' to '0' is a common and valid method. The code checks boundaries and stops recursion correctly.

3. Final Answer:

   It correctly marks visited cells by setting '1' to '0', no bug -> Option C

4. Quick Check:

   Mark visited by changing '1' to '0' is correct [OK]

Hint: Mark visited by changing '1' to '0' is valid [OK]

Common Mistakes:

• Thinking grid modification is always wrong
• Expecting separate visited array
• Confusing diagonal neighbors as required

5. You have a grid with 1000 rows and 1000 columns filled mostly with '0's and a few scattered '1's forming small islands. Which approach is best to efficiently count islands and why?

hard

A. Use BFS with a queue to avoid deep recursion and handle large grid efficiently

B. Use DFS with recursion because it is simpler and faster for large grids

C. Use DFS but do not mark visited cells to save memory

D. Count '1's directly without traversal to save time

Solution

1. Step 1: Consider grid size and recursion limits

   A 1000x1000 grid is large. Recursive DFS may cause stack overflow due to deep recursion.

2. Step 2: Evaluate BFS advantages for large grids

   BFS uses an explicit queue and avoids deep recursion, making it safer and efficient for large grids.

3. Step 3: Check other options for correctness

   DFS without marking visited causes infinite loops. Counting '1's directly misses island grouping.

4. Final Answer:

   Use BFS with a queue to avoid deep recursion and handle large grid efficiently -> Option A

5. Quick Check:

   Large grid + avoid recursion overflow = BFS [OK]

Hint: Use BFS to avoid recursion limits on large grids [OK]

Common Mistakes:

• Using recursive DFS causing stack overflow
• Not marking visited cells causing infinite loops
• Counting '1's without grouping