图论作为数学的一个重要分支,在计算机科学中也扮演着非常重要的角色。随着大数据时代的到来,图数据的规模也随之增大,因此图算法的效率对于解决图论问题至关重要。由于现实问题中可能会遇到很多的意外情况,如机器故障,信号传输的不稳定性等,最终导致实际数据存在不确定性。因此不确定图已经成为一个非常热门的研究领域。本文对不确定图中的生成树算法进行了研究,主要获得了如下成果:(1)由于不确定图的边存在不确定性,所以传统的最小生成树定义已经不能完全适用于不确定图。因此提出了最优生成树的概念,它主要是在最小生成树定义的基础上增加了对概率的最优化定义。然后我们借助贪心的思想设计了不确定图中最优生成树算法。(2)为了能够找到不确定图中的所有关键边,我们设计了Top-K最小生成树算法,并提出了基于并查集的优化算法和基于启发式搜索的优化算法。当值较小时,基于启发式搜索的优化算法具有明显的优势。(3)对最小生成树在不确定图中的可靠性进行了分析。将可靠性定义为所有包含最小生成树的蕴含图的存在概率之和,主要使用了边集划分的方法将所有蕴含图进行归类,在同一类中的蕴含图具有相同的最小生成树,通过求同一类中所有蕴含图存在的概率来获得不确定图的可靠性。(4)针对不确定有向图,给出了最优树形图的定义,设计了最优树形图算法。最后将TOP-K最小生成树算法的思想和最优树形图的性质相结合设计了TOP-K最小树形图查询算法。最后,我们对不确定图中生成树的研究进行了相关的实验验证,实验结果表明,设计的算法的运行效率与理论分析基本一致,且能够完全正确的得到问题的解。