基础

bfs，广度优先搜索，按照字面意思，以一个点出发，“一圈一圈”地向外搜索。
其基本形态是

var st []bool // 标记是否访问过

func bfs(start int) {
   q := []int{start} // bfs特征：候选队列
   st[start] = true
   for len(q) > 0 { // 候选队列处理完为止
       t := q[0]; q = q[1:] // 取队头
        for .... { // 按照某种规则，从该点扩展
            if !st[nx] && ... { // 扩展出来的新点未被访问过，且满足某需要的条件
                ... // 处理逻辑
                st[nx] = true // 标记已访问
                q = append(q, nx) // 新扩展的点进入候选队列
            }

        }


   }
}

使用场景：遍历一个二维矩阵

因为要存二维矩阵的下标(i, j)，通常定义一个pair的struct

type pair struct {
    a, b int // a: i, b: j
}

对应的bfs数组自然是：q := []pair{}
而要在二维矩阵上遍历，还得需要二维矩阵偏移数组

dx := [4]int{0, 1, 0, -1}
dy := [4]int{1, 0, -1, 0}

遍历方法：

x, y // 当前点
for i := 0; i < 4; i++ {
    nx := x + dx[i]
    ny := y + dy[i] // [nx, ny]：按照4个方向遍历出来的新点
    ...
}

完整示例：

type pair struct {
    a, b int
}

var (
    st [][]bool // 标记是否已经访问
    g [][]int // 被遍历的矩阵

    dx = [4]int{0, 1, 0, -1}
    dy = [4]int{1, 0, -1, 0}
)

func bfs(x, y int) {
    q := []pair{pair{x, y}}
    st[x][y] = true
    for len(q) > 0 {
        t := q[0]; q = q[1:]
        for i := 0; i < 4; i++ {
            nx := t.a + dx[i]
            ny := t.b + dy[i]
            if ... && !st[nx][ny] && g[nx][ny]... { // 当新的点满足： 没出界 + 未访问 + 某具体条件
                ... // 处理逻辑
                st[nx][ny] = true
                q = append(q, pair{nx, ny})
            }
        }
    }
}

在某些要计算“在有障碍的矩阵上起点到终点的最短距离”，会构建一个与被遍历矩阵等大的dist矩阵，上面的每一格表示从起点到该点的最短距离。如果初始值设为-1，则可表示为当前点未访问，能起到类似st矩阵的作用

type pair struct {
    a, b int
}

var (
    dist [][]int // 距离矩阵
    g [][]int // 被遍历的矩阵

    dx = [4]int{0, 1, 0, -1}
    dy = [4]int{1, 0, -1, 0}
)

func bfs(x, y int) int {
    q := []pair{pair{x, y}}
    for len(q) > 0 {
        t := q[0]; q = q[1:]
        for i := 0; i < 4; i++ {
            nx := t.a + dx[i]
            ny := t.b + dy[i]
            if ... && g[nx][ny]... && dist[nx][ny] == -1 { // 当新的点满足： 没出界 + 某具体条件 + 未访问（dist[nx][ny] == -1）
                ... // 处理逻辑
                dist[nx][ny] = dist[x][y] + 1
                q = append(q, pair{nx, ny})
            }
        }
    }
    return ...
}

func main() {
    ...
    dist[0] = -1; for i := 1; i < N; i *= 2 {copy(dist[i:], dist[:i])} // 在调用bfs之前，先初始化dist矩阵
    dist[0][0] = 0 // 初始化起点[0, 0]
    ...
    bfs()


}

使用场景：遍历邻接数组

这里不用偏移数组，因为邻接数组的h, ne数组就定好了当前点“如何遍历”
遍历方法：

top // 当前点
for j := h[top]; j != -1; j = ne[j] {
    x := e[j] // x： 顺着邻接数组遍历出来的新点
    ...
}

完整示例：

var (
    st []bool

    idx int // 邻接数组标准
    h, e, ne []int // 邻接数组三部件：头数组、值数组、下位数组
)

func add(a, b int) { // 邻接数组加边
    e[idx] = b; ne[idx] = h[a]; h[a] = idx; idx++
}

func bfs(start int) {
    q := []int{start}
    st[start] = true
    for len(q) > 0 {
        t := q[0]; q = q[1:]
        for j := h[t]; j != -1; j = ne[j] { // 顺着邻接数组遍历
            x := e[j]
            if !st[x] { // 当新的点未遍历
                ... // 处理逻辑
                q = append(q, x) // 新点入队
                st[x] = true // 标记已访问
            }
        }
    }
}