Quick find
Quick find, as its name implies, favors having a quick find over union. The data structure keeps an ids element indexed vector used to determine when two elements are in the same component. There is also a count variable to keep the total of connected components:
#[derive(Debug)]
/// QuickFind data structure for solving the dynamic connectivity problem.
pub struct QuickFind {
/// Keeps the number of connected components
count: usize,
/// An element-indexed vector to represent the components. The name of one of the elements in a
/// component will be used as the component identifier.
ids: Vec<usize>,
}Two elements p and q are connected iff ids[p] == ids[q] as we can see in the following code the find implementation is quick because it just returns the element value in the ids vector and the union needs to scan the whole ids vector to properly update all references to the p component with the q one, for each input pair meaning quadratic-time processing:
impl UnionFind for QuickFind {
/// Merges two components if the two elements are in different components.
fn union(&mut self, p: usize, q: usize) {
let p_at = self.find(p);
let q_at = self.find(q);
if p_at != q_at {
for i in &mut self.ids {
if *i == p_at {
*i = q_at;
}
}
self.count -= 1;
}
}
/// Returns the component identifier for a given element.
fn find(&mut self, i: usize) -> usize {
self.ids[i]
}
/// Returns the number of components.
fn components(&self) -> usize {
self.count
}
}The details of how the algorithm process looks like is described in its unit test:
#[test]
fn test_quick_find() {
let mut alg = QuickFind::new(10);
// Initial state: all elements roots are themselves and their root sizes are 1. The total
// components are 10.
let mut expected_find_pos = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
//
assert_eq!(alg.components(), 10);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 4 and 3, both elements have different entry values, 4 and 3 respectively, so they are
// in different components and can be connected so the algorithms changes all references to
// p(4) to q(3). The total components are 9.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 3, 3, 5, 6, 7, 8, 9];
// ^ ^
alg.union(4, 3);
assert_eq!(alg.components(), 9);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 3 and 8, their entry values are 3 and 8 so all references to p(3) which is 3 are
// changed to the value of q(8) which is 8. The total components are 8.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 8, 8, 5, 6, 7, 8, 9];
// ^ ^ ^
alg.union(3, 8);
assert_eq!(alg.components(), 8);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 6 and 5, their entry values are 6 and 5 so all references to p(6) are changed to the
// value of q(5) which is 5. The total components are 7.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 8, 8, 5, 5, 7, 8, 9];
// ^ ^
alg.union(6, 5);
assert_eq!(alg.components(), 7);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 9 and 4, their entry values are 9 and 8 so all references to p(9) are changed to the
// value of q(4) which is 8. The total components are 6.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 2, 8, 8, 5, 5, 7, 8, 8];
// ^ ^
alg.union(9, 4);
assert_eq!(alg.components(), 6);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 2 and 1, their entry values are 2 and 1 so all references to p(2) are changed to the
// value of q(1) which is 1. The total components are 5.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 1, 8, 8, 5, 5, 7, 8, 8];
// ^ ^
alg.union(2, 1);
assert_eq!(alg.components(), 5);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 8 and 9, their entry values are the same so nothing else is needed.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 1, 8, 8, 5, 5, 7, 8, 8];
// ^ ^
alg.union(8, 9);
assert_eq!(alg.components(), 5);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 5 and 0, their entry values are 5 and 0 so all references to p(5) are changed to the
// value of q(0) which is 0. The total components are 4.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 1, 8, 8, 0, 0, 7, 8, 8];
// ^ ^ ^
alg.union(5, 0);
assert_eq!(alg.components(), 4);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 7 and 2, their entry values are 7 and 1 so all references to p(7) are changed to the
// value of q(2) which is 1. The total components are 3.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [0, 1, 1, 8, 8, 0, 0, 1, 8, 8];
// ^ ^
alg.union(7, 2);
assert_eq!(alg.components(), 3);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 6 and 1, their entry values are 0 and 1 so all references to p(6) which is 0 are
// changed to the value of q(1) which is 1. The total components are 2.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [1, 1, 1, 8, 8, 1, 1, 1, 8, 8];
// ^ ^ ^ ^
alg.union(6, 1);
assert_eq!(alg.components(), 2);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 1 and 0, their entry values are the same 1 so nothing else is needed.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [1, 1, 1, 8, 8, 1, 1, 1, 8, 8];
// ^ ^
alg.union(1, 0);
assert_eq!(alg.components(), 2);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
// Union 6 and 7, like in the last iteration their roots are the same 1 so nothing else is
// needed.
// 0 1 2 3 4 5 6 7 8 9
expected_find_pos = [1, 1, 1, 8, 8, 1, 1, 1, 8, 8];
// ^ ^
alg.union(6, 7);
assert_eq!(alg.components(), 2);
for (i, expected_find) in expected_find_pos.into_iter().enumerate() {
assert_eq!(alg.ids[i], expected_find, "i={}", i);
}
}The full source code can be found here.