如何基于Base R实现矩阵中最大连通1区域的大小求解

Hey there! Let's work through this problem of finding the largest connected region of 1s in a binary matrix using just Base R. Depth-First Search (DFS) is exactly the right approach here, and we can build this without any fancy third-party packages—just plain old R functions.

The Problem Recap #

Given a matrix of 0s and 1s, we need to find the size of the largest connected region of 1s (connected means adjacent up/down/left/right; diagonal doesn't count). For example, this matrix:

1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0

has two connected regions of 1s: one with 5 elements, and one with 1. We need to output the maximum size, which is 5.

Core Approach: Depth-First Search #

Here's the plan:

• Iterate over every element in the matrix. If we hit a 1 that hasn't been visited yet, start a DFS traversal.
• For each 1 we visit, mark it as visited (so we don't count it again) and recursively check its four adjacent cells (up, down, left, right).
• Keep a running total of the size of the current connected region.
• Track the largest region size we find across the entire matrix.

Base R Implementation Code #

# DFS helper function to count connected 1s
dfs <- function(matrix, visited, row, col) {
  n_rows <- nrow(matrix)
  n_cols <- ncol(matrix)
  
  # Exit if we're out of bounds, on a 0, or already visited this cell
  if (row < 1 || row > n_rows || col < 1 || col > n_cols || 
      matrix[row, col] != 1 || visited[row, col]) {
    return(0)
  }
  
  # Mark current cell as visited
  visited[row, col] <- TRUE
  
  # Recursively count connected cells in all four directions, plus current cell
  return(1 + 
           dfs(matrix, visited, row - 1, col) +  # Up
           dfs(matrix, visited, row + 1, col) +  # Down
           dfs(matrix, visited, row, col - 1) +  # Left
           dfs(matrix, visited, row, col + 1))   # Right
}

# Main function to find the maximum connected region size
max_connected_ones <- function(matrix) {
  # Edge case: empty matrix
  if (is.null(matrix) || nrow(matrix) == 0 || ncol(matrix) == 0) {
    return(0)
  }
  
  n_rows <- nrow(matrix)
  n_cols <- ncol(matrix)
  # Create a matrix to track visited cells (initialized to FALSE)
  visited <- matrix(FALSE, nrow = n_rows, ncol = n_cols)
  max_size <- 0
  
  # Loop through every cell in the matrix
  for (i in 1:n_rows) {
    for (j in 1:n_cols) {
      if (matrix[i, j] == 1 && !visited[i, j]) {
        current_region_size <- dfs(matrix, visited, i, j)
        # Update max size if current region is larger
        if (current_region_size > max_size) {
          max_size <- current_region_size
        }
      }
    }
  }
  
  return(max_size)
}

Test the Example #

Let's run the function on the sample matrix from the problem:

# Build the test matrix
test_matrix <- matrix(
  c(1,1,0,0,
    0,1,1,0,
    0,0,1,0,
    1,0,0,0),
  nrow = 4, byrow = TRUE
)

# Call the function
max_connected_ones(test_matrix)
# Output: 5

Quick Notes #

• This implementation uses 4-directional connectivity (up/down/left/right). If you need 8-directional (including diagonals), just add four more recursive calls to the DFS function for the diagonal positions.
• The visited matrix ensures we don't reprocess the same cell multiple times, which keeps the algorithm efficient.
• Everything here uses only Base R—no extra packages required, just as requested.

内容的提问来源于stack exchange，提问作者Tony Hellmuth