Lecture Notes: Connected Components Problem

Key Concepts

• BFS and DFS Traversal Techniques
• Application of Traversal in Graph Problems
• Conversion of Grid to Graph Representation
• Problem Statement: Number of Connected Components (Islands) in a Grid

Problem Explanation

• Grid Representation:

  • Size: n x m (n = rows, m = columns)
  • Elements: 0 (water) and 1 (land)

• Objective: Find the number of islands (connected components of land).

  • Island: formed by connecting adjacent lands (horizontally, vertically, or diagonally in all 8 directions).

Graph Representation of Grid

• Consider each element in the grid as a node/vertex.
• Connections between nodes are based on adjacency (8 directions).

Traversal Intuition

• Start at any land node (represented by 1) and perform BFS/DFS traversal.
• Ensure all connected land nodes are visited in one traversal, marking an island.
• Repeat the process for unvisited lands to count remaining islands.

Detailed BFS Traversal Steps

1. Initialization:
   • Create a visited 2D array of same size as grid.
   • Use a queue to handle traversal.
2. Marking and Visiting Nodes:
   • Start with a node and mark it as visited.
   • Push the node into the queue.
3. Neighbor Checking:
   • For each node, check all 8 possible neighbors.
   • Mark valid neighbors (within bounds, land, and not visited) and push them to the queue.
4. Traversal Completion:
   • Continue until the queue is empty - this completes one BFS traversal, indicating one island.

Pseudocode Highlights

• Iterate through the grid, starting BFS for unvisited lands.
• Count number of BFS/DFS calls as the number of islands.
• BFS Function: Handle queue operations, neighbor validation, and marking visiting states.

Space and Time Complexity Analysis

• Space Complexity: O(n imes m) - for the visited array and potential queue size.
• Time Complexity: O(n imes m) - covering all nodes and checking neighbors.

Key Takeaways

• The problem can be visualized as traversing a graph with nodes and edges based on grid connections.
• BFS and DFS are interchangeable for this problem, with detailed implementation relying on queue operations and neighbor checks.