Kruskal最小生成树算法

图算法

Kruskal算法是一种贪心算法,用于寻找加权无向图的最小生成树,它按照边的权重从小到大排序,并依次添加不会形成环的边。

时间复杂度:最佳 O(E log E) | 平均 O(E log E) | 最差 O(E log E)
空间复杂度:O(V + E)
图类型:加权图

应用场景/前提条件

  • 只适用于连通的无向加权图

算法讲解

Kruskal最小生成树算法

介绍

Kruskal算法是一种用于带权无向图的最小生成树算法,该算法基于贪心策略,通过选择权值最小的边构建最小生成树。

最小生成树是图中连接所有顶点的一个子图,它是一棵树(无环连通图),且所有边的权重总和最小。

算法步骤

  1. 将图中所有边按权重从小到大排序
  2. 创建一个森林(每个顶点初始时是一棵独立的树)
  3. 按排序后的顺序处理每条边(u, v):
    • 如果顶点u和v不在同一个连通分量中(即不在同一棵树中)
    • 则将这条边加入最小生成树中
    • 合并包含u和v的两棵树(连通分量)
  4. 重复步骤3,直到最小生成树包含图中所有顶点(即V-1条边,其中V是顶点数)

算法详解

以共有6个顶点(A-F)和10条边的带权无向图为例:

  • A-B:权重3
  • A-C:权重1

...