Skip to main content

par_connected_components

Function par_connected_components 

Source
pub fn par_connected_components<T>(
    graph: &Graph<T, impl Clone + Send + Sync>,
) -> Vec<Vec<NodeIndex>>
where T: Clone + Send + Sync,
Expand description

并行连通分量(基于并查集)

注意:由于并行并查集的实现复杂性,这里使用简化版本:

  1. 边的处理是并行的
  2. 但 union 操作使用原子操作保证安全性
  3. find 操作使用迭代而非递归避免栈溢出

注意:此实现在多核上可能不会带来显著加速,因为并查集本质上是串行的