Kruskal是另一个计算最小生成树的算法，其算法原理如下。首先，将每个顶点放入其自身的数据集合中。然后，按照权值的升序来选择边。当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，就移动到下一条边。重复这个过程直到所有的边都探查过。
struct Node //作为数据结构存储图
{int start;int end;int length;
};思路很简单，代码实现也很简单。以结构体数组作为存储结构存储该图的信息，结构体由它所连接的两个顶点和边的权值构成。首先对边的权值排序，这个使用封装好的sort函数就行了，再就是选边过程。
图我找了一个（懒癌晚期，见笑了）。
用算法思路描述该过程就是从小到大依次选边，若选中的边的两个顶点都已经加入到树中，则不选取该边，只要两个边有一个没有在树中的就把这条边加入到树中，相应的这两个顶点不管之前是0个或是1个已经在树中，此时都认为这两个顶点都已经在树中，遍历结束则得到最小生成树。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Node //作为数据结构存储图
{int start;int end;int length;
};
bool compare(Node a, Node b)
{return a.length < b.length;
}
void Kruskal(vector<Node> &arr, vector<bool> &visited)
{int M, N;M = visited.size();N = arr.size();for (int i = 0; i < N; i++){cin >> arr[i].start >> arr[i].end >> arr[i].length;}sort(arr.begin(), arr.end(), compare);int weight = 0;for (int i = 0; i < N; i++){if (!visited[arr[i].start] || !visited[arr[i].end]){weight += arr[i].length;visited[arr[i].start] = true;visited[arr[i].end] = true;}}cout << "最小生成树权值为:";cout << weight << endl;
}
int main()
{int M,N;cin>>M>> N;vector<Node> arr(N);vector<bool> visited(M);Kruskal(arr,visited);
}
/*
作为测试用例送你们了
6 8
0 1 2
0 2 1
1 3 5
2 3 4
1 2 3
2 4 1
4 5 2
3 5 3
最小生成树权值为9
*/代码最下面的注释就作为测试用例送你们了，不要谢我?( ????` )比心