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

81次阅读
没有评论

前言

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

01000
11100
10000
00010

在上述的二维网格中,岛屿数量为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就像是撞了南墙多年后释怀了的年轻人,再往那平静的湖面扔一块石头而周围泛起那一波波涟漪。

6
憧憬Licoy
版权声明:本站原创文章,由憧憬Licoy2021-07-30发表,共计1550字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
载入中...