Breadth-First Search

グラフ探索

グラフ・木構造を「近い頂点から順に」探索するアルゴリズム。深さ優先探索(DFS)がスタック (再帰)で「行けるところまで先に進む」のに対し、BFSはキュー(FIFO)で「現在地から1歩の範囲を全部見てから2歩目へ進む」を繰り返す。

計算量

O(V + E)(V=頂点数、E=辺数)。全頂点・全辺をちょうど1回ずつ処理するだけなので、グラフが大きくなってもコストは線形にしか増えない。

なぜ必要か

辺の重みがすべて1(無向・無重みグラフ)のとき、BFSで頂点を訪問した順序はそのまま startからの最短距離(最小の手数)になる。迷路の最短手数、SNSの「友達の友達」検索、知恵の輪的なパズルの最小手数など、「最小手数・最短経路」を求める問題の定番。蟻本2-4節、アルゴリズム図鑑「幅優先探索」で扱われる基礎アルゴリズム。

DFSとの使い分け:

BFS(キュー) — 最短距離・最小手数を求めたいとき
DFS(スタック/再帰) — 全経路の列挙・連結成分の判定・トポロジカルソートなど

具体例

次の無向グラフで頂点1からBFSする:

graph TD
  n1((1)) --- n2((2))
  n1((1)) --- n3((3))
  n2((2)) --- n4((4))
  n3((3)) --- n4((4))
  n4((4)) --- n5((5))

キューの中身は [1] → [2,3] → [3,4] → [4] → [5] → [] と変化し、訪問順は 1 → 2 → 3 → 4 → 5。distを見ると、1から5へは3手(1→2→4→5 または 1→3→4→5)が最短だとわかる。

Java

まだJava版はありません。

キューは []int をスライスの先頭切り出し(queue[0], queue[1:])で代用している (学習用の小規模グラフが前提のため。件数が増える用途ではcontainer/list等に置き換えたい)。

実行: go run ./Algorithms/patterns/BFS/go

$ go run ./Algorithms/patterns/BFS/go

graph.go

package main

// Graph は隣接リスト表現の無向グラフ(頂点ID -> 隣接頂点IDのリスト)。
type Graph map[int][]int

// BFS は startから幅優先探索し、訪問順(order)と startからの最短距離(dist、辺の本数)を返す。
//
// 計算量: O(V+E)(V=頂点数、E=辺数)。全頂点・全辺をちょうど1回ずつ処理するだけなので、
// グラフが大きくなってもコストは線形にしか増えない。
// 辺の重みが全て1(無向・無重み)のとき、訪問順にキューへ積んでいくBFSの性質上、
// distはそのまま「startからの最短手数」になる(深さ優先探索(DFS)ではこれは成り立たない)。
func BFS(g Graph, start int) (order []int, dist map[int]int) {
	dist = map[int]int{start: 0}
	queue := []int{start}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:] // ponytail: 学習用の小規模グラフ前提でO(n)切り出し。件数が増えたらcontainer/list等に置き換え
		order = append(order, node)
		for _, next := range g[node] {
			if _, seen := dist[next]; !seen {
				dist[next] = dist[node] + 1
				queue = append(queue, next)
			}
		}
	}
	return order, dist
}

main.go

package main

import "fmt"

// 実行: go run ./Algorithms/patterns/BFS/go
func main() {
	g := Graph{
		1: {2, 3},
		2: {1, 4},
		3: {1, 4},
		4: {2, 3, 5},
		5: {4},
	}
	order, dist := BFS(g, 1)
	fmt.Println("訪問順:", order)
	for node := 1; node <= 5; node++ {
		fmt.Printf("dist(1, %d) = %d\n", node, dist[node])
	}
}

PHP

まだPHP版はありません。

TypeScript

まだTypeScript版はありません。

Python

まだPython版はありません。