Boruvka 알고리즘 병렬 구현 CUDA

Question

CUDA의 최소 스패닝 트리에 대해 Boruvka's algorithm을 구현하려고합니다. 기본 논리는 이해하지만 구현하는 데 문제가 있습니다. 이 알고리즘은 다음과 같습니다

Initialize Graph G(V,E) 
Initialize MST 
while size(G) > 1: 
    for all nodes in graph: 
    min equals minimum outgoing edge 
    ? 

나는 각 노드의 최소 나가는 가장자리를 계산 한 후, 나는 새로운 노드에 연결되지 않은 서브 그래프를 줄이는 방법을 이해하지 않습니다. 이렇게하면이 분리 된 하위 그래프 사이의 최소 가장자리는 어떻게 계산합니까?

Answer 1

나는 새로운 노드로 분리 된 부분 그래프를 줄일 필요가 없다고 생각한다. 노드가 속해 있는지 (최소한 나가는 에지를 계산할 때) 각 노드의 새로운 구성 요소를 재 계산해야한다. 다른 구성 요소. This 데이터 구조는 효과적인 방법으로이를 수행하는 데 도움이됩니다.

disjoint 서브 그래프 사이의 최소 에지 계산을 위해 일반적으로 reduction이 사용됩니다. 나는 이것을 위해 다른 커널을 시작해야한다고 생각한다.