01-BFSについて
01-BFSは最短路アルゴリズムの一種で、辺のコストが$ 0か$ 1のどちらか、という場合に使える
計算量はBFSと同じ$ O(N+M)($ N:頂点数、$ M:辺数)
BFSではキューを用意し、以下のような操作を行う
毎ステップ、頂点をキューの先頭から取り出し、今いる頂点とする
今いる頂点に隣接する頂点が未到達ならキューの末尾に追加する
(素直な実装)
01BFSではキュー(スタックでも可)をふたつ用意し、以下のような操作を行う
このとき、キューは0-キュー、1-キューという名前をつけることにする
1-キューにある頂点の最短路長は、0-キューにある頂点の最短路長$ +1である
毎ステップ、以下の操作を行う
0-キューが空なら、0-キューと1-キューを交換する(コピーが発生しないように注意、ポインタの交換を使うべき)
0-キューから頂点をひとつ取り出し、今いる頂点とする
今いる頂点に隣接する頂点が未到達なら
コストが$ 0のときは0-キューに追加する
コストが$ 1のときは1-キューに追加する
(工夫した実装)
キューやスタックをふたつ用意するかわりに、Deque(両端キュー)を使うこともできる
毎ステップ、以下の操作を行う
Dequeの先頭から頂点をひとつ取り出し、今いる頂点とする
今いる頂点に隣接する頂点が未到達なら
コストが$ 0のときはDequeの先頭に追加する
コストが$ 1のときはDequeの末尾に追加する
素直な実装でも工夫した実装でも計算量は変わらない(定数倍は工夫した実装のほうが良いかも)
ただし、素直な実装はキューの個数を増やすことで辺のコストが$ 0, 1, 2, 3, \ldotsの場合に対応できる
(コストの上限が$ Kの場合、キューを$ K+1個用意し、計算量は$ O(NK+M)となる)
これはDial's Algorithmと呼ばれる
さらに、Dial's Algorithmを01-BFSの工夫した実装のように、複数のキューのかわりにひとつの優先度付きキューを使うと、ダイクストラ法になる
(おまけ)Rustによる実装
code:rust
// 01-BFSの素直な実装
fn bfs_01(graph: Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> {
let mut queue = [vec!start, vec![]]; let mut queued_count = 1;
while queued_count != 0 {
while let Some(u) = queue0.pop() { queued_count -= 1;
for &(v, cost) in &graphu { let next_dist = distu.saturating_add(cost); queued_count += 1;
}
}
}
queue.swap(0, 1);
}
dist
}
// Dial's Algorithm (上限を最初に求めず、足りなくなったら追加する)
let mut queue = std::collections::VecDeque::new();
queue.push_back(vec!start); let mut queued_count = 1;
while queued_count != 0 {
while let Some(u) = queue0.pop() { queued_count -= 1;
for &(v, cost) in &graphu { let next_dist = distu.saturating_add(cost); // キューが足りなかったら追加する
for _ in queue.len() ..= cost {
queue.push_back(vec![]);
}
queued_count += 1;
}
}
}
queue.rotate_left(1);
}
dist
}