Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我正在尝试在 CUDA 中实现Boruvka 的最小生成树算法。我理解基本逻辑,但我无法实现它。算法是:
Initialize Graph G(V,E) Initialize MST while size(G) > 1: for all nodes in graph: min equals minimum outgoing edge ?
在计算每个节点的最小出边之后,我不明白如何将不相交的子图减少为新节点。一旦我这样做了,我如何计算这些不相交的子图之间的最小边?
我认为您不必将不相交的子图减少为新节点,您只需为每个节点重新计算其新组件,以便能够区分(在计算最小传出边期间)该节点是否属于不同的组件。这种数据结构将帮助您以有效的方式做到这一点。
对于不相交子图之间的最小边的计算,通常使用约简。我认为您将不得不为此启动另一个内核。