介绍
Kruskal算法是一种最小生成树算法，用于在带有权重的连通图中找到最小生成树。一个连通图由一组节点和连接这些节点的边组成，每条边都有一个权重。
Kruskal算法的基本思想是：
从边的权重从小到大进行排序，然后依次考虑每条边。在考虑每条边时，判断当前的边是否会形成环路，如果不会形成环路，则将该边加入最小生成树的边集合中。
具体算法步骤如下：
1. 初始化一个空的最小生成树边集合。
2. 将所有边按照权重从小到大排序。
3. 依次考虑每条边，判断当前边的两个端点是否已经在最小生成树的边集合中，如果不在则将该边加入最小生成树的边集合中。
4. 继续下一条边的考虑，直到最小生成树的边数达到节点数减1或者所有边都考虑完毕。
Kruskal算法的时间复杂度主要取决于对边进行排序的部分，通常使用的排序算法是快速排序或者归并排序，时间复杂度为O(ElogE)，其中E为边的数量。
总结一下，Kruskal算法以贪心的方式逐步构建最小生成树，它的优点在于简单易懂且实现相对容易，适用于边稀疏的图。
举例
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 边的结构体 struct Edge { int src, dest, weight; }; // 并查集的数据结构 struct DisjointSet { vector<int> parent; void init(int n) { parent.resize(n); for (int i = 0; i < n; i++) { parent[i] = i; } } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void merge(int x, int y) { int rootX = find(x); int rootY = find(y); parent[rootX] = rootY; } }; bool compareEdges(Edge& edge1, Edge& edge2) { return edge1.weight < edge2.weight; } void kruskal(vector<Edge>& edges, int n) { sort(edges.begin(), edges.end(), compareEdges); DisjointSet ds; ds.init(n); vector<Edge> minimumSpanningTree; int edgeCount = 0; int i = 0; while (edgeCount < n - 1 && i < edges.size()) { Edge& currentEdge = edges[i]; int srcParent = ds.find(currentEdge.src); int destParent = ds.find(currentEdge.dest); if (srcParent != destParent) { minimumSpanningTree.push_back(currentEdge); ds.merge(srcParent, destParent); edgeCount++; } i++; } cout << "边\t权重\n"; for (const auto& edge : minimumSpanningTree) { cout << edge.src << " - " << edge.dest << "\t" << edge.weight << "\n"; } } int main() { int n, m; cout << "输入节点数："; cin >> n; cout << "输入边数："; cin >> m; vector<Edge> edges(m); cout << "输入每条边的起点、终点和权重：\n"; for (int i = 0; i < m; i++) { cin >> edges[i].src >> edges[i].dest >> edges[i].weight; } kruskal(edges, n); return 0; }
这个例子中，首先定义了边的结构体Edge，然后定义了并查集的数据结构DisjointSet，并实现了并查集的初始化、查找和合并操作。接下来，通过比较边权重的函数compareEdges来对边进行排序。然后，在kruskal函数中，先对边进行排序，然后使用并查集来判断边的两个端点是否在同一个连通分量中，如果不在，则将边加入最小生成树中，并合并这两个端点为同一个连通分量。最后，输出最小生成树的边和权重。
在main函数中，首先读取节点数和边数，然后逐个读取每条边的起点、终点和权重。最后调用kruskal函数来计算最小生成树。
