不确定图上最小生成树的可靠性评估

摘要:最小生成树是连接整个网络的最小成本的生成树,但无法在不确定图上直接获得。 在本文中,我们将可靠性定义为所有最小生成树的存在概率,并提出了一种在不确定图上评估最小生成树的可靠性的算法。 该算法的时间复杂度为O(Nmn),其中n,m和N分别代表顶点数,边数和最小生成树。 由于该算法花费更多的时间查找最小生成树,因此我们提出了一种改进的算法,其时间复杂度为O(Nm)。 改进的算法使用了不相交的集合数据结构,因此找到新的最小生成树时的平均时间复杂度为O(m / n)。 对这两种算法进行了详细分析,实验结果与理论分析吻合。