在Swift中实现一维数组的连通分量（Connected Components）查找

我懂你这种转语言时卡壳的感觉——把JS里找连通分量的逻辑搬到Swift确实得适应下Swift的数组处理和语法细节。我之前做过类似的需求，给你整理了两种常用的实现方式：DFS（深度优先搜索）和BFS（广度优先搜索），都是针对一维数组对应二维网格找"1"的连通区域的场景（假设一维数组是二维网格按行扁平化的结果，需要传入列数来计算x/y坐标）。

核心思路 #

不管用哪种算法，核心逻辑都是一致的：

• 先把一维数组映射为二维网格的坐标（根据列数计算每个元素的x、y位置）
• 用一个标记数组记录每个位置是否已经被处理过，避免重复加入连通分量
• 遍历每个位置，遇到未访问的"1"时，就收集所有和它连通的"1"的坐标，形成一个分量
• 连通规则默认用4连通（上下左右），如果需要8连通（含对角线），只需要增加方向数组即可

DFS实现（递归方式） #

递归写法代码更简洁，适合小规模网格：

// 定义坐标元组，方便存储x/y位置
typealias Coordinate = (x: Int, y: Int)

func findConnectedComponentsDFS(grid: [String], columns: Int) -> [[Coordinate]] {
    // 边界检查：空数组或列数非法直接返回空
    guard !grid.isEmpty, columns > 0 else { return [] }
    
    let rows = grid.count / columns
    // 校验一维数组长度是否符合 rows * columns，避免逻辑错误
    guard grid.count == rows * columns else {
        print("Error: Grid length doesn't match rows * columns")
        return []
    }
    
    // 标记数组：记录每个位置是否已被访问
    var visited = Array(repeating: Array(repeating: false, count: columns), count: rows)
    // 存储所有连通分量
    var components: [[Coordinate]] = []
    
    // 4连通方向：上下左右
    let directions: [Coordinate] = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    // 如果需要8连通，把下面四个方向加上即可
    // let directions: [Coordinate] = [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    
    // 递归DFS函数，收集当前坐标所在的连通分量
    func dfs(x: Int, y: Int, currentComponent: inout [Coordinate]) {
        // 边界校验：坐标越界、已访问、不是"1"则直接返回
        guard x >= 0, x < columns, y >= 0, y < rows,
              !visited[y][x],
              grid[y * columns + x] == "1" else {
            return
        }
        
        // 标记为已访问，加入当前分量
        visited[y][x] = true
        currentComponent.append((x, y))
        
        // 遍历所有方向，递归处理邻居
        for dir in directions {
            dfs(x: x + dir.x, y: y + dir.y, currentComponent: &currentComponent)
        }
    }
    
    // 遍历每个位置，寻找未访问的"1"
    for y in 0..<rows {
        for x in 0..<columns {
            if grid[y * columns + x] == "1" && !visited[y][x] {
                var currentComponent: [Coordinate] = []
                dfs(x: x, y: y, currentComponent: &currentComponent)
                components.append(currentComponent)
            }
        }
    }
    
    return components
}

BFS实现（队列方式） #

如果网格规模很大，递归DFS可能会触发栈溢出，这时候用BFS（队列）更安全：

typealias Coordinate = (x: Int, y: Int)

func findConnectedComponentsBFS(grid: [String], columns: Int) -> [[Coordinate]] {
    guard !grid.isEmpty, columns > 0 else { return [] }
    
    let rows = grid.count / columns
    guard grid.count == rows * columns else {
        print("Error: Grid length doesn't match rows * columns")
        return []
    }
    
    var visited = Array(repeating: Array(repeating: false, count: columns), count: rows)
    var components: [[Coordinate]] = []
    let directions: [Coordinate] = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    
    for y in 0..<rows {
        for x in 0..<columns {
            if grid[y * columns + x] == "1" && !visited[y][x] {
                var currentComponent: [Coordinate] = []
                // 用队列存储待处理的坐标
                var queue: [Coordinate] = [(x, y)]
                visited[y][x] = true
                
                // 处理队列中的所有坐标
                while !queue.isEmpty {
                    let current = queue.removeFirst()
                    currentComponent.append(current)
                    
                    // 遍历所有方向，检查邻居
                    for dir in directions {
                        let newX = current.x + dir.x
                        let newY = current.y + dir.y
                        if newX >= 0, newX < columns, newY >= 0, newY < rows,
                           !visited[newY][newX],
                           grid[newY * columns + newX] == "1" {
                            visited[newY][newX] = true
                            queue.append((newX, newY))
                        }
                    }
                }
                
                components.append(currentComponent)
            }
        }
    }
    
    return components
}

使用示例 #

假设我们有一个一维数组对应3行3列的网格：

一维数组：["1","1","0","0","1","0","1","1","1"]
对应二维网格：
1 1 0
0 1 0
1 1 1

调用函数获取连通分量：

let grid = ["1","1","0","0","1","0","1","1","1"]
let components = findConnectedComponentsDFS(grid: grid, columns: 3)
print(components)
// 输出结果：
// [[(x: 0, y: 0), (x: 1, y: 0), (x: 1, y: 1)], [(x: 0, y: 2), (x: 1, y: 2), (x: 2, y: 2)]]

如果你的一维数组和二维网格的映射关系不同（比如按列扁平化），只需要调整y * columns + x这个索引计算逻辑即可。

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