广度优先搜索

图

说明

用队列逐层扩展；无权图中的首次到达即最短步数。

分析

队列按发现先后处理节点，第一次到达一个节点的层数就是无权图最短距离。dist 用 −1 表示尚未访问，并同时充当 visited 标记。

图解推演

正文链 0→1→2 的层数为 0、1、2。更一般地，一个点首次入队时就赋距离并标记，保证同层的多个父节点不会反复把它入队。队列保留先进先出顺序是按边数最短的关键，改成栈就不再有这个保证。

查看图表代码

适用前提与边界

边有不同权重时首次到达不一定最优，应使用合适的带权最短路算法。

示例输入与调用

fmt.Println(BFS([][]int{{1}, {2}, {}}, 0))

运行输出

[0 1 2]

完整 Go 示例

package main

import "fmt"

func BFS(g [][]int, start int) []int {
	dist := make([]int, len(g))
	for i := range dist {
		dist[i] = -1
	}
	dist[start] = 0
	q := []int{start}
	for h := 0; h < len(q); h++ {
		v := q[h]
		for _, w := range g[v] {
			if dist[w] < 0 {
				dist[w] = dist[v] + 1
				q = append(q, w)
			}
		}
	}
	return dist
}

func main() {
	fmt.Println(BFS([][]int{{1}, {2}, {}}, 0))
}