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

807次阅读
没有评论

前言

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

01000
11100
10000
00010

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

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 就像是撞了南墙多年后释怀了的年轻人,再往那平静的湖面扔一块石头而周围泛起那一波波涟漪。

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