Kruskal 算法

Kruskal 算法是计算机科学中用于求图的最小生成树的常用方法，由 Joseph Kruskal 于 1956 年提出。该算法首先将图的各条边按权重升序排序，然后逐一遍历这些边，如果某条边与已加入生成树的边不构成回路，就将其加入生成树。这一过程不断重复，直到图中所有顶点都包含在树中为止。Kruskal 算法属于贪心算法一类，因为它在每个阶段都力求局部最优，以期最终获得全局最优。它的整体时间复杂度为 O(E log E) 或 O(E log V)，其中 E 是边数，V 是顶点数。