algorithmica 0.1.9

Rust Algorithms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

use crate::graph::Graph;

#[allow(clippy::upper_case_acronyms)]
pub struct BFS<'a> {
    #[allow(dead_code)]
    source: usize,
    visited: Vec<bool>,
    parent: Vec<usize>,
    dist: Vec<usize>,
    graph: &'a Graph,
}

impl<'a> BFS<'a> {
    pub fn new(source: usize, graph: &'a Graph) -> Self {
        let mut new = Self {
            source,
            visited: vec![false; graph.v],
            parent: vec![0; graph.v],
            dist: vec![0; graph.v],
            graph,
        };
        new.bfs(source);
        new
    }

    pub fn has_path(&self, w: usize) -> bool {
        self.visited[w]
    }

    pub fn dist(&self, w: usize) -> usize {
        self.dist[w]
    }

    fn bfs(&mut self, source: usize) {
        let queue = vec![source];
        self.visited[source] = true;
        self.dist[source] = 0;
        self.parent[source] = 0; // TODO: Fix Me
        while !queue.is_empty() {
            let front = queue.first().unwrap();
            for w in self.graph.adj(*front).iter() {
                if !self.visited[*w] {
                    self.visited[*w] = true;
                    self.dist[*w] = self.dist[*front] + 1;
                    self.parent[*w] = *front;
                }
            }
        }
    }
}