Kruskal最小生成树算法

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

  1. Kruskal算法
  2. Prim算法
Kruskal算法 一种为连接的加权图构造最小生成树的算法。这是一个贪婪算法。贪婪的选择是将最小的重量边缘放置, 这并不是因为到目前为止已构造的MST中的一个循环。
如果该图未链接, 则它将找到最小生成树。
使用Kruskal算法查找MST的步骤:
  1. 按重量增加的顺序排列G的边缘。
  2. 仅从G的顶点开始, 依次进行相加, 直到不使用循环, 直到使用(n-1)个边为止。
  3. 出口。
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算法找到下图的最小生成树。
Kruskal最小生成树算法

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

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

步骤2:然后(g, f)边缘。
Kruskal最小生成树算法

文章图片
步骤3:然后考虑(a, b)和(i, g)边, 森林变成
Kruskal最小生成树算法

文章图片
步骤4:现在, 边缘(h, i)。 h和i顶点在同一集合中。因此, 它创建了一个循环。因此, 该边缘被丢弃。
然后考虑边(c, d), (b, c), (a, h), (d, e), (e, f), 森林就变成了。
Kruskal最小生成树算法

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

文章图片
步骤7:将需要最小生成树, 因为它包含所有9个顶点并且(9-1)= 8个边
e → f, b → h, d → f [cycle will be formed]

Kruskal最小生成树算法

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

    推荐阅读