克鲁斯卡尔算法，就是每次将最小的边的权值加入到最小生成树中，并不形成环，最后形成的树就是最小生成树，比如下面的题目中的图：
最小生成树的过程：
第一步：1-2
第二步：1-3
第三步：0-1
第四步：3-2形成环1-2-3不行，所以1-8
第五步：4-3
....剩余其他都会形成环的
问题：求一个图的最小生成树
输入n组边的数据，输入m，标识m个顶点
接下来的n行标识n组边的数据，格式是a b c,a标识这个边的起点，b标识边的尾点，c标识这个边的权值
例如，对下面的一个图，进行输入：
输入：
10 6
0 1 6
1 2 3
3 2 7
1 3 5
0 4 10
4 3 9
0 5 12
1 5 8
4 5 16
3 5 11
思路：
1，定义一个边的结构体，因为有权值，单独定义更有利于后面的思路拓展
typedef struct edge{//定义一条边
int start;//定义开始节点
int end;//定义结束节点
int weight;//定义这条边的权值
};
2，因为输入边的数据，所以定义一个边的数组，并对这个数组的权值进行从小到大排序
3，定义一个k[m][m]的一个二维数组，用来存储有效的边，也就是最终的最小生成树，初始化为0，i,j对应每个边的起点和终点，数组中的值表示边的权值
4，依次将排序过后的edge数组中的数据进行判断，如果加入的这条边和前面的边没有形成环，就加入到k中，否则遍历下一个边
5，我认为难点在于如何判断无向图是否有环，之前了解过有向图的，对于无向图的，难住我了，最终发现一个不错的方法
使用set<int> m；来做那就是看当前的这条边是否在m中，如果在，说明形成环了，跳过，如果不在，就将这个边的起点和终点都加入到m中，因为set可以自动排序和去重，所以非常方便
if (st1.find(e[i].start) != st1.end() && st1.find(e[i].end) != st1.end())//end()是最后一个元素的下一个元素
continue;
else{
k[e[i].start][e[i].end] =e[i].weight;//k存放的是组成最小生成树的边
st1.insert(e[i].start);
st1.insert(e[i].end);
}
6，遍历k数组，就可以看到最终的最小生成树，用二维数组来标识
有了思路，代码很好写的
代码：
#include <iostream>
#include<stack>
#include <set>
using namespace std;
typedef struct edge{//定义一条边
int start;//定义开始节点
int end;//定义结束节点
int weight;//定义这条边的权值
};
int zhixing(edge *e,int low,int high){
int i=low;
int j=high;
edge key=e[i];
while(i<j){
while(i<j&&e[j].weight>=key.weight){
j--;
}
if(i<j){
e[i++]=e[j];
}
while(i<j&&e[i].weight<=key.weight){
i++;
}
if(i<j){
e[j--]=e[i];
}
}
e[i]=key;
return i;
}
void kp(edge *e,int low,int high){
if(low<high){
int key=zhixing(e,low,high);
kp(e,low,key-1);
kp(e,key+1,high);
}
}
bool tuopu(int **p,int n){//有环，返回true
int k[n];
for(int i=0;i<n;i++){
k[i]=0;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]!=0){
k[i]++;
}
}
}
stack<int> s;
//将k中<=1的存到栈中
for(int i=0;i<n;i++){
if(k[i]<=1){
s.push(i);
}
}
while(!s.empty()){
int i=s.top();
//cout<<i<<" ";
s.pop();
for(int j=0;j<n;j++){
if(p[i][j]!=0){
k[j]--;
if(k[j]==1){
s.push(j);
}
}
}
}
for(int i=0;i<n;i++){
if(k[i]>=2){
//cout<<k[i]<<" ";
return true;
}
}
return false;
}
int main()
{
//克鲁斯卡尔算法，求最小生成树
int n,m;//输入n组边的信息,m个顶点
cin>>n>>m;
//定义边的数组
edge *e=new edge[n];
//输入边的信息
for(int i=0;i<n;i++){
cin>>e[i].start;
cin>>e[i].end;
cin>>e[i].weight;
}
//对边的权值按照从小到大进行排序，使用快速排序方法
kp(e,0,n-1);
//定义有关顶点的二维数组，用来存储边//初始化为0
int **k=new int*[m];
for(int i=0;i<m;i++){
k[i]=new int[m];
}
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
k[i][j]=0;
}
}
//每次将排序过后的边的依次加入k中，同时看加入之后是否形成环，如果形成环就置为0
//判断无向图是否是环，采用拓扑排序的方法，具体操作，上面有注释
for(int i=0;i<n;i++){
k[e[i].start][e[i].end] =e[i].weight;//k存放的是组成最小生成树的边
k[e[i].end][e[i].start] =e[i].weight;//因为是无向图，所以最终形成的是一个对称的二维数组
if (tuopu(k,m)){//如果k是环，就将刚刚置为数字的重新置为0
k[e[i].start][e[i].end] =0;
k[e[i].end][e[i].start] =0;
}
}
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
cout<<k[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
结果：
