希赛教育计算机专业考研专业课辅导招生
希赛教育计算机专业考研专业课辅导视频
希赛教育计算机考研专业课在线测试系统
克鲁斯卡尔算法的基本思想为为使生成树上总的权值之和达到最小则应使每一条边上的权值尽可能地小自然应从权值最小的边选起直至选出n条互不构成回路的权值最小边为止具体作法如下首先构造一个只含n个顶点的森林然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去直至该森林变成一棵树为止这棵树便是连通网的最小生成树
由于生成树上不允许有回路因此并非每一条居当前权值最小的边都可选例如在依次选中了(ef)(bc)(ed) 和 (fg) 的四条边之后权值最小边为 (gd)由于 g 和 d 已经连通若加上(gd) 这条边将使生成树上产生回路显然这条边不可取同理边 (fd) 也不可取之后则依次取 (ag) 和 (ab) 两条边加入到生成树
