导读 关于克鲁斯卡尔算法的时间复杂度是多少,什么是克鲁斯卡尔算法这个问题很多朋友还不知道,今天小六来为大家解答以上的问题,现在让我们一起
关于克鲁斯卡尔算法的时间复杂度是多少,什么是克鲁斯卡尔算法这个问题很多朋友还不知道,今天小六来为大家解答以上的问题,现在让我们一起来看看吧!
1、计算最小生成树的算法克鲁斯卡尔算法 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。
2、之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。
3、依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。
本文分享完毕,希望对大家有所帮助。
标签:
免责声明:本文由用户上传,如有侵权请联系删除!