haar_lib/graph/
bfs.rs

1//! 幅優先探索
2
3use crate::graph::*;
4use std::collections::VecDeque;
5use std::iter::zip;
6
7/// 幅優先探索で辺数が最小の経路を得る。
8pub fn bfs<D: Direction, E: EdgeTrait>(
9    g: &Graph<D, E>,
10    src: impl IntoIterator<Item = usize>,
11) -> Vec<Option<(usize, Option<&E>)>> {
12    let mut dist = vec![None; g.len()];
13    let mut prev = vec![None; g.len()];
14    let mut check = vec![false; g.len()];
15    let mut q = VecDeque::new();
16
17    for s in src {
18        dist[s] = Some(0);
19        q.push_back(s);
20    }
21
22    while let Some(cur) = q.pop_front() {
23        if check[cur] {
24            continue;
25        }
26        check[cur] = true;
27
28        let d_cur = dist[cur].unwrap();
29        for e in g.nodes[cur].edges.iter() {
30            let to = e.to();
31            if dist[to].is_none_or(|d| d > d_cur + 1) {
32                dist[to] = Some(d_cur + 1);
33                prev[to] = Some(e);
34                q.push_back(to);
35            }
36        }
37    }
38
39    zip(dist, prev).map(|(a, b)| a.map(|a| (a, b))).collect()
40}
haar_lib/graph/bfs.rs

haar_lib/graph/
bfs.rs
