2

CUDA の最小スパニング ツリーにBoruvka のアルゴリズムを実装しようとしています。基本的なロジックは理解していますが、実装に問題があります。アルゴリズムは次のとおりです。

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

各ノードの最小出力エッジを計算した後、ばらばらのサブグラフを新しいノードに削減する方法がわかりません。それを行ったら、これらのばらばらのサブグラフ間の最小エッジを計算するにはどうすればよいですか?

4

1 に答える 1

1

ばらばらのサブグラフを新しいノードに減らす必要はないと思います。ノードが異なるコンポーネントに属しているかどうかを（最小出力エッジの計算中に）区別できるようにするには、ノードごとにその新しいコンポーネントを再計算する必要があります。このデータ構造は、効果的な方法でそれを行うのに役立ちます。

互いに素なサブグラフ間の最小エッジの計算には、通常、リダクションが使用されます。これには別のカーネルを起動する必要があると思います。

于 2012-12-10T13:26:13.630 に答える