ac_lib/graph/
bfs.rs

1use std::collections::VecDeque;
2
3pub fn bfs(graph: &[Vec<usize>], start: usize, visited: &mut [bool]) -> Vec<usize> {
4    let mut queue = VecDeque::new();
5    let mut order = Vec::new();
6
7    visited[start] = true;
8    queue.push_back(start);
9
10    while let Some(node) = queue.pop_front() {
11        order.push(node);
12
13        for &neighbor in &graph[node] {
14            if !visited[neighbor] {
15                visited[neighbor] = true;
16                queue.push_back(neighbor);
17            }
18        }
19    }
20
21    order
22}
23
24pub fn bfs_with_callback<F>(
25    graph: &[Vec<usize>],
26    start: usize,
27    visited: &mut [bool],
28    callback: &mut F,
29) where
30    F: FnMut(usize),
31{
32    let mut queue = VecDeque::new();
33
34    visited[start] = true;
35    queue.push_back(start);
36
37    while let Some(node) = queue.pop_front() {
38        callback(node);
39
40        for &neighbor in &graph[node] {
41            if !visited[neighbor] {
42                visited[neighbor] = true;
43                queue.push_back(neighbor);
44            }
45        }
46    }
47}
ac_lib/graph/bfs.rs

ac_lib/graph/
bfs.rs
