克鲁斯卡尔算法构造最小生成树

红色为结点,黑色为带权

用克鲁斯卡尔算法构造最小生成树。

首先将最小的的边选上,即2–3,如图:

看绿线

找其他最小的边, 即2–1,如图:

找其他最小的边, 即1–4,如图:

找其他最小的边 ,有两条最小的边,一条4–3,一条1–5,前面那条舍去,因为跟前面的结点形成了回路, 如图:

依次类推,

克鲁斯卡尔算法也叫加边法。

最后一步算下带权 ,我考试的时候忘记写了 , 扣了几分 , WPL=3+4+5+6+7+8=33

赞赏

微信赞赏支付宝赞赏

发表评论