Debugging breadth-first search (BFS) implementation

王林

Release： 2024-02-10 15:18:19

forward

876 people have browsed it

调试广度优先搜索 (BFS) 的实现

php editor Youzi introduces to you the implementation of debugging Breadth First Search (BFS). Breadth-first search is a traversal algorithm for graphs and trees that starts from a starting node and visits adjacent nodes layer by layer until the target node is found. When implementing the BFS algorithm, debugging is a very important link. It can help us find errors and logical problems in the code and improve the efficiency and accuracy of the program. This article will introduce you in detail how to debug the BFS algorithm, hoping to be helpful to your learning and practice.

Question content

Background

I have 3d voxels in 3d space. They are indexed by x, y, z. They are labeled full or empty. I'm trying to efficiently count the number of components consisting of neighbor full voxels.

bfs details

I have the following code to implement the breadth first search (bfs) algorithm. Each voxel is represented by [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
}

Copy after login

question

The above implementation does not work properly. For a simple model that should only contain 8 components, it returns a component count of 1224:

question

I stepped through the code through the vs code debugger. But I can't figure out this error. Does anyone see anything suspicious in the code? Any tips to point me in the right direction?

Workaround

The problem is that you are also calling bfs on empty voxels.

In countcomponents, verified bfs is only called on voxels that have not been visited yet (good):

if !visited[[3]int{x, y, z}] {

Copy after login

...but it's missing a test to see if the voxel is full (bad), and bfs will happily add it to the queue expecting it to be full. Therefore, Each empty voxel is also counted as one (1 voxel size) component.

The above is the detailed content of Debugging breadth-first search (BFS) implementation. For more information, please follow other related articles on the PHP Chinese website!