c++ Kruskal 最小生成树 (MST) 算法（Kruskal’s Minimum Spanning Tree (MST) Algorithm）

        对于加权、连通、无向图，最小生成树(MST) 或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。

Kruskal算法简介：
        在这里，我们将讨论Kruskal 算法来查找给定加权图的 MST。 

        在 Kruskal 算法中，按升序对给定图的所有边进行排序。然后，如果新添加的边不形成循环，它会继续在 MST 中添加新边和节点。它首先选择最小权重边，最后选择最大权重边。因此，我们可以说它在每一步中都做出局部最优选择以找到最优解。因此，这是一种贪婪算法。

如何使用 Kruskal 算法查找 MST？
以下是使用 Kruskal 算法查找 MST 的步骤：

1.按照权重的非递减顺序对所有边进行排序。 
2.选择最小的边。检查它是否与目前形成的生成树形成一个循环。如果没有形成循环，则包括这条边。否则，丢弃它。 
3.重复步骤#2，直到生成树中有 (V-1) 条边。

第 2 步使用并查集算法来检测循环。 
因此，我们建议先阅读以下文章：

并查表算法 | 集合 1（检测图中的循环） 

javascript 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524938

C# 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524824

python 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524698

java 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524698

c++ 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142523025

并查集算法 | 集合 2（按秩并集和路径压缩）

c语言 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526674

javascript 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526517

C# 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526449

python 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526387

java 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526336

c++ 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142525945

        Kruskal 寻找最小成本生成树的算法采用贪婪方法。贪婪选择是选择迄今为止构建的 MST 中不会引起循环的最小权重边。让我们通过一个例子来理解它：

插图：
下面是上述方法的说明：

输入图：

该图包含 9 个顶点和 14 条边。因此，形成的最小生成树将具有 (9 - 1) = 8 条边。 

排序后： 

现在从排序的边列表中逐一选择所有边 

步骤 1：选取边 7-6。未形成循环，将其包括在内。

步骤 2：拾取边 8-2。未形成循环，将其包括在内。    

步骤 3：选取边 6-5。未形成循环，将其包括在内。  

步骤 4：选取边 0-1。没有形成循环，将其包括在内。  

步骤 5：选取边 2-5。未形成循环，将其包括在内。 

步骤 6：选择边 8-6。由于包含此边会导致循环，因此将其丢弃。选择边 2-3：未形成循环，因此将其包括在内。 

步骤 7：选择边 7-8。由于包含此边会导致循环，因此将其丢弃。选择边 0-7。未形成循环，因此将其包括在内。   

步骤 8：选择边 1-2。由于包含此边会导致循环，因此将其丢弃。选择边 3-4。未形成循环，因此将其包括在内。 

注意：由于MST中包含的边数等于（V-1），因此算法在此停止

下面是上述方法的实现： 

// C++ program for the above approach 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// DSU data structure 
// path compression + rank by union 
class DSU { 
    int* parent; 
    int* rank; 
  
public: 
    DSU(int n) 
    { 
        parent = new int[n]; 
        rank = new int[n]; 
  
        for (int i = 0; i < n; i++) { 
            parent[i] = -1; 
            rank[i] = 1; 
        } 
    } 
  
    // Find function 
    int find(int i) 
    { 
        if (parent[i] == -1) 
            return i; 
  
        return parent[i] = find(parent[i]); 
    } 
  
    // Union function 
    void unite(int x, int y) 
    { 
        int s1 = find(x); 
        int s2 = find(y); 
  
        if (s1 != s2) { 
            if (rank[s1] < rank[s2]) { 
                parent[s1] = s2; 
            } 
            else if (rank[s1] > rank[s2]) { 
                parent[s2] = s1; 
            } 
            else { 
                parent[s2] = s1; 
                rank[s1] += 1; 
            } 
        } 
    } 
}; 
  
class Graph { 
    vector<vector<int> > edgelist; 
    int V; 
  
public: 
    Graph(int V) { this->V = V; } 
  
    // Function to add edge in a graph 
    void addEdge(int x, int y, int w) 
    { 
        edgelist.push_back({ w, x, y }); 
    } 
  
    void kruskals_mst() 
    { 
        // Sort all edges 
        sort(edgelist.begin(), edgelist.end()); 
  
        // Initialize the DSU 
        DSU s(V); 
        int ans = 0; 
        cout << "Following are the edges in the "
                "constructed MST"
             << endl; 
        for (auto edge : edgelist) { 
            int w = edge[0]; 
            int x = edge[1]; 
            int y = edge[2]; 
  
            // Take this edge in MST if it does 
            // not forms a cycle 
            if (s.find(x) != s.find(y)) { 
                s.unite(x, y); 
                ans += w; 
                cout << x << " -- " << y << " == " << w 
                     << endl; 
            } 
        } 
        cout << "Minimum Cost Spanning Tree: " << ans; 
    } 
}; 
  
// Driver code 
int main() 
{ 
    Graph g(4); 
    g.addEdge(0, 1, 10); 
    g.addEdge(1, 3, 15); 
    g.addEdge(2, 3, 4); 
    g.addEdge(2, 0, 6); 
    g.addEdge(0, 3, 5); 
  
    // Function call 
    g.kruskals_mst(); 
  
    return 0; 
}

输出

以下是构建的 MST 中的边
2 -- 3 == 4 
0 -- 3 == 5 
0 -- 1 == 10

最小成本生成树：19

时间复杂度： O（E * logE）或O（E * logV） 

    1.边的排序需要 O(E * logE) 时间。 

    2.排序后，我们遍历所有边并应用查找并集算法。查找和并集操作最多需要 O(logV) 时间。

    3.因此总体复杂度为 O(E * logE + E * logV) 时间。 

    4.E 的值最多为 O(V 2 )，因此 O(logV) 和 O(logE) 相同。因此，总体时间复杂度为 O(E * logE) 或 O(E*logV)

辅助空间： O（V + E），其中 V 是图中顶点的数量，E 是边的数量。