Guided Project: Graphs III

Master advanced graph applications with a focus on floodfill algorithms and practical implementations using arrays and loops.

Advanced Graph Applications

In this advanced module, we'll explore practical applications of graph algorithms, focusing on floodfill algorithms and their implementation using arrays and loops. These techniques are essential for solving real-world problems in image processing, game development, and maze solving.

Key Concepts

Floodfill algorithm implementation
2D array traversal techniques
Efficient loop-based solutions

Learning Objectives

Master floodfill algorithm implementation
Optimize array-based graph solutions
Apply graph concepts to practical problems

Implementation Techniques

Floodfill Implementation

While-Loops and Arrays

What is Floodfill?

Floodfill is an algorithm that determines and modifies the area connected to a given node in a multi-dimensional array. It's commonly used in:

Image editing software's "bucket fill" tool
Game development for territory capture
Maze solving algorithms
Connected component analysis

Implementation Steps

Set Up Grid Structure

Initialize 2D array and define boundary conditions

// Example 2D grid representation
int[][] grid = {
    {1, 1, 1, 1, 1},
    {1, 0, 0, 0, 1},
    {1, 0, 1, 0, 1},
    {1, 0, 0, 0, 1},
    {1, 1, 1, 1, 1}
};

// Define directions for adjacent cells (up, right, down, left)
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

Implement Floodfill Logic

Create recursive or iterative fill algorithm

Recursive Implementation

public void floodFillRecursive(int[][] grid, int row, int col, int originalColor, int newColor) {
    // Check boundary conditions
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) {
        return;
    }
    
    // Check if current cell needs to be filled
    if (grid[row][col] != originalColor) {
        return;
    }
    
    // Fill current cell
    grid[row][col] = newColor;
    
    // Recursively fill adjacent cells
    floodFillRecursive(grid, row - 1, col, originalColor, newColor); // Up
    floodFillRecursive(grid, row, col + 1, originalColor, newColor); // Right
    floodFillRecursive(grid, row + 1, col, originalColor, newColor); // Down
    floodFillRecursive(grid, row, col - 1, originalColor, newColor); // Left
}

Iterative Implementation (Using Queue)

public void floodFillIterative(int[][] grid, int row, int col, int originalColor, int newColor) {
    // Check if starting point is valid
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) {
        return;
    }
    
    // If starting cell is not the target color or already the new color
    if (grid[row][col] != originalColor || grid[row][col] == newColor) {
        return;
    }
    
    // Create queue for BFS
    Queue queue = new LinkedList<>();
    queue.add(new int[]{row, col});
    grid[row][col] = newColor;
    
    // Define directions (up, right, down, left)
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    
    // BFS to fill connected cells
    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int r = current[0];
        int c = current[1];
        
        // Check all four adjacent cells
        for (int i = 0; i < 4; i++) {
            int newRow = r + dx[i];
            int newCol = c + dy[i];
            
            // Check if adjacent cell is valid and has the original color
            if (newRow >= 0 && newRow < grid.length && 
                newCol >= 0 && newCol < grid[0].length && 
                grid[newRow][newCol] == originalColor) {
                
                // Fill and add to queue
                grid[newRow][newCol] = newColor;
                queue.add(new int[]{newRow, newCol});
            }
        }
    }
}

Optimize Performance

Implement efficient array traversal techniques

Use a visited array to avoid revisiting cells (especially for large grids)
Early termination when the target is found (for pathfinding)
Direction arrays to simplify adjacent cell iteration
Precompute grid boundaries to reduce boundary checks

// Optimized using a visited array
public void floodFillOptimized(int[][] grid, int row, int col, int newColor) {
    int originalColor = grid[row][col];
    if (originalColor == newColor) return; // No need to fill
    
    int rows = grid.length;
    int cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    
    Queue queue = new LinkedList<>();
    queue.add(new int[]{row, col});
    visited[row][col] = true;
    
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    
    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int r = current[0];
        int c = current[1];
        
        // Fill the current cell
        grid[r][c] = newColor;
        
        for (int i = 0; i < 4; i++) {
            int newRow = r + dx[i];
            int newCol = c + dy[i];
            
            if (newRow >= 0 && newRow < rows && 
                newCol >= 0 && newCol < cols && 
                !visited[newRow][newCol] && 
                grid[newRow][newCol] == originalColor) {
                
                visited[newRow][newCol] = true;
                queue.add(new int[]{newRow, newCol});
            }
        }
    }
}

Visual Example: Floodfill Process

Let's visualize a floodfill operation on a 5x5 grid, starting at position (1,1) changing value 0 to 2:

Initial Grid

Step 1: Fill (1,1)

Step 2: Fill (1,2)

Step 3: Fill (1,3)

Continue process...

The floodfill algorithm continues until all connected cells with value 0 are filled.

Final Grid

Common Applications

1. Finding Connected Components

public int countConnectedComponents(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    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]) {
                // New component found
                count++;
                floodFillVisit(grid, i, j, visited);
            }
        }
    }
    
    return count;
}

private void floodFillVisit(int[][] grid, int row, int col, boolean[][] visited) {
    int rows = grid.length;
    int cols = grid[0].length;
    
    // Check if out of bounds or already visited or not part of a component
    if (row < 0 || row >= rows || col < 0 || col >= cols || 
        visited[row][col] || grid[row][col] != 1) {
        return;
    }
    
    // Mark as visited
    visited[row][col] = true;
    
    // Visit all adjacent cells
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    
    for (int i = 0; i < 4; i++) {
        floodFillVisit(grid, row + dx[i], col + dy[i], visited);
    }
}

2. Maze Solving

public List solveMaze(int[][] maze, int[] start, int[] end) {
    int rows = maze.length;
    int cols = maze[0].length;
    boolean[][] visited = new boolean[rows][cols];
    
    // Path reconstruction - store parent cell for each visited cell
    Map parent = new HashMap<>();
    
    // BFS to find shortest path
    Queue queue = new LinkedList<>();
    queue.add(start);
    visited[start[0]][start[1]] = true;
    
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    
    boolean foundPath = false;
    
    while (!queue.isEmpty() && !foundPath) {
        int[] current = queue.poll();
        
        // Check if we've reached the end
        if (current[0] == end[0] && current[1] == end[1]) {
            foundPath = true;
            break;
        }
        
        // Try all four directions
        for (int i = 0; i < 4; i++) {
            int newRow = current[0] + dx[i];
            int newCol = current[1] + dy[i];
            
            // Check if valid move
            if (newRow >= 0 && newRow < rows && 
                newCol >= 0 && newCol < cols && 
                !visited[newRow][newCol] && 
                maze[newRow][newCol] == 0) { // 0 represents an open path
                
                // Mark as visited and add to queue
                visited[newRow][newCol] = true;
                queue.add(new int[]{newRow, newCol});
                
                // Store parent for path reconstruction
                parent.put(newRow + "," + newCol, current);
            }
        }
    }
    
    // Reconstruct path if found
    List path = new ArrayList<>();
    if (foundPath) {
        int[] current = end;
        while (current[0] != start[0] || current[1] != start[1]) {
            path.add(current);
            current = parent.get(current[0] + "," + current[1]);
        }
        path.add(start);
        Collections.reverse(path);
    }
    
    return path;
}

Practice Exercises

Exercise 1: Basic Floodfill

Implement a basic floodfill algorithm to fill a connected region in a 2D grid.

public void floodFill(int[][] grid, int row, int col, int newColor) {
    // Your implementation here
    // Hint: Use either recursive DFS or iterative BFS approach
    // Don't forget to check boundary conditions!
}

Exercise 2: Island Counter

Count the number of isolated regions (islands) in a 2D grid using floodfill.

public int countIslands(int[][] grid) {
    // Your implementation here
    // Hint: Iterate through the grid, when you find a land cell (1),
    // increment counter and use floodfill to mark the entire island as visited
}

Exercise 3: Maze Solver

Implement a maze solver using floodfill to find a path from start to end.

public List solveMaze(int[][] maze, Point start, Point end) {
    // Your implementation here
    // Hint: Use BFS to find the shortest path, and track the path using a parent map
}

Exercise 4: Calculate Area

Use floodfill to calculate the area of a connected region in a grid.

public int calculateArea(int[][] grid, int row, int col) {
    // Your implementation here
    // Hint: Count the number of cells filled during floodfill
}

Exercise 5: Boundary Fill

Implement a boundary fill algorithm that fills a region until it reaches a specified boundary color.

public void boundaryFill(int[][] grid, int row, int col, int fillColor, int boundaryColor) {
    // Your implementation here
    // Hint: Similar to floodfill, but stop when you hit the boundary color
}

Exercise 6: Advanced - Diagonal Floodfill

Implement a floodfill algorithm that considers 8 directions (including diagonals) instead of just 4.

public void diagonalFloodFill(int[][] grid, int row, int col, int newColor) {
    // Your implementation here
    // Hint: Use 8 directions instead of 4 (add the 4 diagonal directions)
}

Graphs III: Advanced Applications