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

红色为结点,黑色为带权

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

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

看绿线

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

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

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

依次类推,

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

赞赏

微信赞赏支付宝赞赏

124 次阅读量

发表评论