多处理器上求最小生成树的并行算法

摘要

目的给出无向图Ｇ（Ｖ，Ｅ），｜Ｖ｜＝ｎ的最小生成树在单指令流多数据流（ＳＩＭＤ）机器、Ｉｎｃｏｍｐｌｅｔｅ－ｈｙｐｅｒｃｕｂｅ上的并行算法．方法利用有ｐ个处理器的不完全超立方网络，求加权无向连通图Ｇ（Ｖ，Ｅ），｜Ｖ｜＝ｎ的最小生成树．结果与结论若处理器的个数为ｐ，则其时间复杂性为ｔ（ｎ）＝Ｏ（ｎ２／ｐ·（ｌｂｐ）），成本Ｃ（ｎ）＝Ｏ（ｎ２（ｌｂｐ）），它几乎是最优的．