岛屿数量计算中的DFS和BFS的应用

8次阅读
没有评论

共计 1554 个字符,预计需要花费 4 分钟才能阅读完成。

前言

计算岛屿数量是在由’0’与’1’的二维网格中寻找竖直的上下左右被’1’包围的岛屿数量(如果是多个’1’连接在一起,则算作一个岛屿),如:

01000111001000000010

在上述的二维网格中,岛屿数量为 2,图解岛屿的具体分布为:
岛屿数量计算中的 DFS 和 BFS 的应用

DFS 方式

对于计算岛屿数量可以采用 DFS 的方式进行解决,由 [0,0] 开始,依次进行目标点的上下左右四个点搜索其值为’1’的单元,即为 (r+1,c) ,(r-1,c)(r,c+1)(r,c-1), 如遇到非’1’的则返回,将遇到’1’的也要进行改变为’0’,避免重复搜索,进而导致无限递归循环,Golang 实现:

package main import "fmt" func lands(grid [][]byte) int {res := 0    for r, row := range grid {        for c, v := range row {            if v == '1' {dfs(grid, r, c)                res++            }        }    }    return res} func dfs(grid [][]byte, r, c int) {if !(r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0])) {return}    if grid[r][c] != '1' {return}    grid[r][c] = '0'    dfs(grid, r+1, c)    dfs(grid, r-1, c)    dfs(grid, r, c+1)    dfs(grid, r, c-1)} func main() {grid := [][]byte{{'0','1','0','0','0'},        {'1','1','1','0','0'},        {'1','0','0','0','0'},        {'0','0','0','0','1'},    }    fmt.Printf("岛屿的数量为:%d\n", lands(grid))}

运行输出为:

 岛屿的数量为:2

BFS 方式

使用广度优先搜索,其思路和 DFS 有些类似,不同的是搜索的方式不一样,其区别在于 BFS 是使用一个队列,取出首部的节点  (r,c)  判断是否为未越界并且为’1’,若是则将此点的上下左右节点加入队列等待判断,若不是则跳过此节点,如:

package main import "fmt" func lands(grid [][]byte) int {res := 0    for r, row := range grid {        for c, v := range row {            if v == '1' {bfs(grid, r, c)                res++            }        }    }    return res} func bfs(grid [][]byte, r, c int) {queue := [][]int{{r, c},    }    for len(queue) > 0 {r = queue[0][0]        c = queue[0][1]        queue = queue[1:]        if r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) && grid[r][c] == '1' {grid[r][c] = '0'            queue = append(queue, [][]int{{r + 1, c},                {r - 1, c},                {r, c + 1},                {r, c - 1},            }...)        }    }} func main() {grid := [][]byte{{'0', '1', '0', '0', '0'},        {'1', '1', '1', '0', '0'},        {'1', '0', '0', '0', '0'},        {'0', '0', '0', '0', '1'},    }    fmt.Printf("岛屿的数量为:%d\n", lands(grid))}

总结

DFS 和 BFS 都是搜索算法,其主要区别为 DFS 利用递归的方式实现,而 BFS 使用队列的方式实现。归结到现实生活中来解释这两种的算法的规则就如:DFS 中就像一个固执不己的年轻人坠入爱河,不撞南墙不回头。而 BFS 就像是撞了南墙多年后释怀了的年轻人,再往那平静的湖面扔一块石头而周围泛起那一波波涟漪。

正文完
 0
litao2024
版权声明:本站原创文章,由 litao2024 于2024-06-06发表,共计1554字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
验证码