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

我認爲您不必將不相交的子圖減少爲新節點，只需要爲每個節點重新計算其新組件，以便能夠區分（在計算最小輸出邊時）節點是否屬於不同的組件。數據結構將幫助你以有效的方式做到這一點。

爲了計算不相交子圖之間的最小邊，通常使用reduction。我想你必須爲此啓動另一個內核。