我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019跑狗图高清彩图 > 正确性 >

请教prim算法正确性的证明

归档日期:07-13       文本归类:正确性      文章编辑:爱尚语录

  为了减少不必要的麻烦,可以不妨设图中所有边的权重都不同,这样最小生成树是唯一的

  设在生成G的过程中第一次产生的不在T中的边是e,而在G中去掉e得到的两个连通分支记为V1和V2,那么e连接了V1和V2

  把e加入T之后会出现环,在这个环里面V1的顶点和V2的顶点至少还被另一条边f连接(否则T本身就不连通了),由Prim算法的贪心策略可知e比f权重低,那么在T里面把f换成e可得一个总权重更小的生成树,与T的最小性矛盾

本文链接:http://gilbertpromos.com/zhengquexing/415.html