最小生成树----Kruskal

Kruskal与Prim不同的是Prim是以任意一个点为起点，一次向其他点遍历，而Kruskal则是以边为起点，向其他边遍历,Kruskal的时间复杂度远远小于Prim。

思路：

先将所有的边排序
依次找出边权最小的边，并查集判断他是否以连接
如果未连接，则将其连接，并继续找剩下的最小的边
直到边数为(n-1)
```
        时间复杂度O(nlogn)
```

Code

#include<iostream>
#include<memory.h>//memset的头文件
#include<algorithm>//快速排序的头文件
using namespace std;
const int N=2e5+5;
int ans;
int n,m;//顶点数与边数
int fa[N];//并查集的父域
struct edge{
    int u,v;//边的起点与终点
    int cost;//边的权值
}e[N];
bool cmp(edge a,edge b)//结构体比较大小的函数
{
    return a.cost<b.cost;
}
void init(int n)//并查集初始化
{
    for(int i=1;i<=n;i++)
    fa[i]=i;
    return ;
}
int find(int x)//并查集函数
{
    if(fa[x]==x)
    return x;
    else 
    {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
int kruskal(int n,int m)
{
    int e_n=0;//已经建立的边数
    init(n);//初始化
    sort(e,e+m,cmp);//排序
    for(int i=1;i<=m-1;i++)
    {
        int fau=find(e[i].u);//边的起点的父域
        int fav=find(e[i].v);//边的终点的父域
        if(fau!=fav)//如果两个父域不同，则证明他们两个点未连接
        {
            fa[fau]=fav;//讲两个点连接起来
            ans+=e[i].cost;//讲边权累加
            //cout<<e[i].cost<<' ';
            e_n++;//边数加1
            if(e_n==n-1) break; //如果边数到达了n-1，则退出循环
        }    
    }
    if(e_n!=n-1) return -1;//判断是否构成一颗生成树
    else return 1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    e[i].cost=9999;//给每条边初始化最大值
    for(int i=1;i<=m;i++)
    {
        int w;
        cin>>e[i].u>>e[i].v>>w;
        e[i].cost=min(w,e[i].cost);//防止有重复输入的数据，取最小的
    }    
    if(kruskal(n,m)==-1) cout<<"orz"<<endl;
    else cout<<ans<<endl;
    return 0;
}

最小生成树--Kruskal

最小生成树----Kruskal

思路：

Code