BFS
キーワード
概要
グラフの探索アルゴリズム。
主に、探索の始点となる頂点から、各頂点への最短経路を求めるために用いる。
任意の頂点を一つ選び、その頂点に隣接する頂点をキューに追加する。 キューから銭湯の頂点を一つ取り出し、その隣接する頂点を調べる。 もし探索済みならスキップして、そうでないなら新しくキューに追加する。
これを繰り返すことで、全ての連結した頂点を調べることができる。
計算量
BFS によって探索するグラフの頂点数を , 辺の数を とすると、
応用例
- グラフの二点間の到達可能性
- グラフの連結成分の個数
- 二部グラフ判定
- トポロジカルソート
- サイクル検出
実装
頂点 1 からの最短経路を求める実装
q := queue.New[int]()
q.Push(1)
ds := make([]int, n+1)
for i := 1;i <= n;i++{
ds[i] = -1
}
ds[1] = 0
for !q.Empty() {
v := q.Front()
q.Pop()
for _, u := range g[v] {
if ds[u] == -1 {
ds[u] = ds[v] + 1
}
}
}