Kruskal最小生成树算法

2022-04-20 IT知识

有两种查找最小生成树的方法

Kruskal算法
Prim算法

Kruskal算法一种为连接的加权图构造最小生成树的算法。这是一个贪婪算法。贪婪的选择是将最小的重量边缘放置, 这并不是因为到目前为止已构造的MST中的一个循环。
如果该图未链接, 则它将找到最小生成树。
使用Kruskal算法查找MST的步骤：

按重量增加的顺序排列G的边缘。
仅从G的顶点开始, 依次进行相加, 直到不使用循环, 直到使用（n-1）个边为止。
出口。

MST- KRUSKAL (G, w) 1. A ← ? 2. for each vertex v ∈ V [G] 3. do MAKE - SET (v) 4. sort the edges of E into non decreasing order by weight w 5. for each edge (u, v) ∈ E, taken in non decreasing order by weight 6. do if FIND-SET (μ) ≠ if FIND-SET (v) 7. then A←A ∪ {(u, v)} 8. UNION (u, v) 9. return A

分析：其中E是图形中的边数, V是顶点数, 可以显示Kruskal算法在O（E log E）时间或简单地在O（E log V）时间中运行, 所有这些操作都很简单数据结构。这些运行时间是等效的, 因为：

E最多为V2, log V2 = 2 x log V为O（log V）。
如果忽略孤立的顶点, 它们将成为最小生成树的每个组成部分, V≤2 E, 则对数V为O（对数E）。

因此, 总时间为

O (E log E) = O (E log V).

例如：使用Kruskal算法找到下图的最小生成树。

文章图片
解决方案：首先我们将集合A初始化为空集合并创建| v |。树, 每个树包含一个带有MAKE-SET过程的顶点。然后按不减小的权重将E中的边缘排序。
有9个顶点和12个边。因此形成的MST（9-1）= 8个边

文章图片
现在, 检查每个边缘（u, v）端点u和v是否属于同一棵树。如果它们这样做, 则边缘（u, v）不能作为补充。否则, 两个顶点属于不同的树, 并且将边（u, v）添加到A, 并且通过合并过程将两个树中的顶点合并。
第一步：所以, 先取（h, g）边

步骤2：然后（g, f）边缘。

文章图片
步骤3：然后考虑（a, b）和（i, g）边, 森林变成

文章图片
步骤4：现在, 边缘（h, i）。 h和i顶点在同一集合中。因此, 它创建了一个循环。因此, 该边缘被丢弃。
然后考虑边（c, d）, （b, c）, （a, h）, （d, e）, （e, f）, 森林就变成了。

文章图片
步骤5：在（e, f）边缘中, 端点e和f都存在于同一棵树中, 因此将其丢弃。然后（b, h）沿, 它还会创建一个循环。
步骤6：在那条边（d, f）之后, 最后的生成树显示为黑线。

文章图片
步骤7：将需要最小生成树, 因为它包含所有9个顶点并且（9-1）= 8个边

e → f, b → h, d → f [cycle will be formed]

文章图片
【Kruskal最小生成树算法】最低费用MST

推荐阅读

上一篇：最小生成树的应用

下一篇：Prim算法-最小生成树算法