最小生成树之Kruskal(克鲁斯卡尔)贪心算法

本文共702个字,预计阅读时间需要2分钟。

基本思想:(1)构造一个只含n个顶点,边集为空的子图。若将图中各个顶点看成一棵树的根节点,则它是一个含有n棵树的森林。(2)从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图。也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之(3)依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。
大白话:(1)将图中的所有边都去掉。(2)将边按权值从小到大的顺序添加到图中,保证添加的过程中不会形成环(3)重复上一步直到连接所有顶点,此时就生成了最小生成树。这是一种贪心策略。

难点:判断某条边<u, v>的加入是否会在已经选定的边集集合中形成环。
解决办法:使用并查集,分别找出两个顶点u, v所在树的根节点。若根节点相同,说明u, v在同一棵树中,则u, v连接起来会形成环;若根节点不同,则u, v不在一棵树中,连接起来不会形成环,而是将两棵树合并。

克鲁斯卡尔算法的时间复杂度为O(eloge)(e为网中边的数目),因此它相对于普里姆算法而言,适合于求边稀疏的网的最小生成树。
克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{∮}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。

代码:

 

读者评分
[评分人数: 0 平均分: 0]

评论

OmegaXYZ