幅優先探索 (BFS: Breadth-First Search)

「スタートに近い頂点から順番に探索していく」アルゴリズム。

使い所

実装ポイント

キューを使い通ったノードを記録する

参考

BFS

daylight

実装の流れ

頂点1からxまでの最短経路を dist[x] = ? に初期化
キューに頂点1を追加し、dist[1] = 0 にする
キューが空になるまで以下を繰り返す
a. キューの戦闘要素 pos を取得し、削除する
b. posと隣接するすべての未確定頂点 to に対し、dist[to] = dist[pos] + 1にしたあと、キューにtoを追加する
(※ dist[x] = ?のような頂点を未確定頂点とする)

daylight

実装例

#!/usr/bin/env ruby
n, m = gets.chomp.split.map(&:to_i)
graph = Array.new(n+1) { [] }
m.times do |i|
  a, b = gets.chomp.split.map(&:to_i)
  graph[a] << b
  graph[b] << a
end

dist = Array.new(n+1, -1)
queue = []
dist[1] = 0
queue << 1

while !queue.empty?
  pos = queue.shift
  graph[pos].each do |to|
    next if dist[to] != -1
    dist[to] = dist[pos] + 1
    queue << to
  end
end

dist.shift
puts dist