克鲁斯卡尔算法 April 15, 2018 算法 首先，克鲁斯卡尔算法是用来求最小生成树的。另一种求最小生成树的算法叫普林姆算法（Prim）。 克鲁斯卡尔算法本质是贪心，每次选取 不与当前已有边构成环 权值最小 的边作为生成树的边。 算法细节 # 判断是否构成环使用并查集 复杂度分析 # 使用并查集的克鲁斯卡尔算法时间复杂度为O(eloge)，其中loge为并查集判断环所需时间，每条边都要判断一次，因此为O(eloge)。