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

2024年 2月 10日 62.1k 0

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

php小编柚子为您介绍调试广度优先搜索(BFS)的实现。广度优先搜索是一种用于图和树的遍历算法,它从起始节点开始,逐层地访问相邻节点,直到找到目标节点。在实现BFS算法时,调试是非常重要的环节,它可以帮助我们发现代码中的错误和逻辑问题,提高程序的效率和准确性。本文将为您详细介绍如何调试BFS算法,希望能对您的学习和实践有所帮助。

问题内容

背景

我在 3d 空间中有 3d 体素。它们由 x, y, z 索引。它们被标记为 fullempty。我尝试有效地计算由邻居 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 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 = 0 && x = 0 && y = 0 && z 登录后复制

问题

上面的实现无法正常工作。对于仅应包含 8 组件的简单模型,它返回组件计数为 1224

问题

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

解决方法

问题是您还在 empty 体素上调用 bfs

countcomponents 中,已验证 bfs 仅在尚未访问的体素上调用(良好):

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

登录后复制

...但它缺少测试该体素是否是 full (不好),并且 bfs 会很乐意将其添加到队列中,期望它是 full。因此,每个 empty 体素也被计为一个(1 体素大小)组件。

以上就是调试广度优先搜索 (BFS) 的实现的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论