6.6.3.3 Prim算法的并行化

  这里只讨论Prim算法的并行化。Prim算法是一个迭代的过程,每次迭代向最小树中增加一个结点,最终编程最小支撑树。因为每加入一个结点后最短路向量d都要发生变化,很难一次选多个结点加入到最短树,这意味着不同的迭代是很难并行化的,但一次迭代过程可以用多个处理器并行完成。