调试广度优先搜索（BFS）的实现

Question

背景

我在 3D 空间中有 3D 体素。它们由

x, y, z

索引。它们被标记为

full

或

empty

。我尝试有效地计算由相邻

full

体素组成的组件数量。

BFS详情

我有以下实现广度优先搜索（BFS）算法的代码。每个体素由

[3]int{x, y, z}

表示。

// Count separate components consisting of disconnected finite elements.
func (vg *VoxelGrid) CountComponents() int {
    // Map key is (x, y, z) index of voxel.
    visited := make(map[[3]int]bool)
    count := 0
    for z := 0; z < vg.Len.Z; z++ {
        for y := 0; y < vg.Len.Y; y++ {
            for x := 0; x < vg.Len.X; x++ {
                if !visited[[3]int{x, y, z}] {
                    count++
                    vg.bfs(visited, [3]int{x, y, z})
                }
            }
        }
    }
    return count
}

// Algorithm: breadth-first search (BFS).
// This is much faster than depth first search (DFS) algorithm.
func (vg *VoxelGrid) bfs(visited map[[3]int]bool, start [3]int) {
    queue := [][3]int{start}
    visited[start] = true

    for len(queue) > 0 {
        v := queue[0]
        queue = queue[1:]

        neighbors := vg.getNeighbors(v)

        for _, n := range neighbors {
            if !visited[n] {
                visited[n] = true
                queue = append(queue, n)
            }
        }
    }
}

// It returns a list of neighbor voxels that are full, i.e. not empty.
func (vg *VoxelGrid) getNeighbors(v [3]int) [][3]int {
    var neighbors [][3]int
    for i := -1; i <= 1; i++ {
        for j := -1; j <= 1; j++ {
            for k := -1; k <= 1; k++ {
                if i == 0 && j == 0 && k == 0 {
                    continue
                }

                x := v[0] + i
                y := v[1] + j
                z := v[2] + k

                if x >= 0 && x < vg.Len.X &&
                    y >= 0 && y < vg.Len.Y &&
                    z >= 0 && z < vg.Len.Z {
                    // Index is valid.
                } else {
                    continue
                }

                // Is neighbor voxel empty or not?
                if vg.IsNotEmpty(x, y, z) {
                    neighbors = append(neighbors, [3]int{x, y, z})
                }
            }
        }
    }
    return neighbors
}

问题

上面的实现不正常工作。对于应该仅具有

1224

组件的简单模型，它返回组件计数为

8

：

问题

我通过 VS Code 调试器单步调试了代码。但我无法找出这个错误。有人在代码中看到任何可疑的东西吗？有什么提示可以指引我正确的方向吗？

Answer 1

在您的

bfs()

函数中，在处理

start

之前，您不会检查

start

是否已被访问。结果，您将有很多重复的匹配（因为您多次处理访问的节点），这解释了为什么当您只是期待

1224

时，您的答案是

8

。