dsalgo 0.3.10

A package for Datastructures and 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
51
52
53
54
55
56
57

// TODO
// use generic minimum queue
// use generic edge type
pub fn mst_prim_sparse(
    v_size: usize,
    undirected_edges: &[(usize, usize, i64)],
) -> Vec<usize> {
    use std::cmp::Reverse;

    let mut g = vec![vec![]; v_size];

    for (i, &(u, v, w)) in undirected_edges.iter().enumerate() {
        g[u].push((v, w, i));

        g[v].push((u, w, i));
    }

    let mut hq = std::collections::BinaryHeap::new();

    hq.push((Reverse(0), 0)); // weight, to
    let mut eid_to: Vec<Option<usize>> = vec![None; v_size];

    let mut visited = vec![false; v_size];

    while let Some((_, u)) = hq.pop() {
        if visited[u] {
            continue;
        }

        visited[u] = true;

        for &(v, w, i) in &g[u] {
            if visited[v]
                || eid_to[v].is_some()
                    && w >= undirected_edges[eid_to[v].unwrap()].2
            {
                continue;
            }

            hq.push((Reverse(w), v));

            eid_to[v] = Some(i);
        }
    }

    eid_to.into_iter().filter_map(|e| e).collect()
}

// TODO
#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}