# go 图的深度遍历 leetcode 200
[leetcode 200岛屿数量](https://leetcode-cn.com/problems/number-of-islands/)
## 使用dfs遍历图,要注意两点
1. dfs要有结束的出口
2. 要找到当前结点的所有子节点
其他的优化就是各种减枝
## code
连通图,将矩阵中的每一个点都看作图的一个节点,只有两个节点的value相同且相邻,这两个节点才是相连的
```go
var row = 0
var col = 0
var d = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
func numIslands(grid [][]byte) int {
res := 0
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
row = len(grid)
col = len(grid[0])
// 初始化参数完毕,
for i :=0; i<row; i++ {
for j := 0; j<col; j++ {
// 减少不必要的dfs
if grid[i][j] == '1' {
res ++
dfs(grid, i, j)
}
}
}
return res
}
// dfs
func dfs (grid [][]byte, x, y int) {
grid[x][y] = '0'
// 潜在的4个子节点
for i:=0; i<4; i++ {
newx := x+d[i][0]
newy := y+d[i][1]
// 出去出界的坐标
if newx >= 0 && newx < row && newy >=0 && newy < col {
// 只要岛屿,'0'就不考虑了
if grid[newx][newy] == '1' {
dfs(grid, newx, newy)
}
}
}
}
```
有疑问加站长微信联系(非本文作者))