不确定图最小生成树算法

摘要

很多领域产生的大量数据都可以很自然地用不确定图模型表示和描述,如蛋白质交互网络、社交网络、无线传感器网络等。本文研究不确定图上最可靠的最小生成树问题,该问题具有广泛的应用价值和研究意义。精确地求解算法需要枚举所有可能的最小生成树并找出其中出现次数最多的那个。因此,枚举开销随着边数增多呈指数增长,当图规模较大时并不可行。为此本文提出了一个时间复杂度为O(d|V|~2)的启发式贪心算法,其中d为最大的顶点度数,|V|为顶点数。实验结果表明,该算法具有较好的效率和较高扩展性。