## Prim算法

//算法核心：找到集合外距离最近的点，用t更新其他点到集合的距离
//          dist[N];表示点i到当前集合的最短边的长度
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510,INF = 0x3f3f3f3f;
int g[N][N];//存储图,表示点i和点j之间边的长度
int dist[N];//表示点i到当前集合的最短边的长度
bool st[N];//节点是否被加入到生成树中
//int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

int prim()
{
    memset(dist,0x3f, sizeof(dist));//初始化距离数组为一个很大的数（10亿左右）
    dist[1] = 0;//从 1 号节点开始生成 

    int res= 0;//存储最小生成树里所有边的长度之和

    //找集合里距离最小的点
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }
        if(i && dist[t] == INF) return INF;//如果不是第一个点且dist[t]==INF,说明当前距离最近的点到集合的距离是正无穷，
        //说明图是不连通的，不存在最小生成树
        st[t] = true;// 选择该点
        if(i)res += dist[t];//只要不是第一个点就累加

        // 用新加入的点更新其余点到生成树的最短边
        for(int j = 1; j <= n; j++)//更新生成树外的点到生成树的距离
        {
            if(dist[j] > g[t][j] && !st[j])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dist[j] = g[t][j];//更新距离
                //pre[j] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }
    return res;
}

/*void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}*/

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    int t=prim();//求最下生成树
    //getPath();//输出路径
    if(t==INF) cout<<"impossible"<<endl;
    else cout<<t<<endl;
    return 0;
}



## kruskal算法

1.将所有边按权重从小到大排序O(mlogm)
2.建立并查集，起初每个点各自构成一个集合
  枚举每条边（a,b）权重是c。如果(a,b)不连通，将这条边加入到集合中，并累加权重c
  若（a，b）连通，忽略这条边，继续扫描吓一条

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=100010,M=200010;         

int p[N];
int n,m;

struct Edge
{
    int a,b,w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;//按权重排序
    }
}edges[M];

int find(int x)//并查集模板
{
    if(p[x]!=x) p[x]=find(p[x]);
    else return x;
} 

int Kruskal()
{
    int res=0,cnt=0;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)

    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        if(find(a)!=find(b))//这两条边不连通，不属于同一集合
        /*
        具体可以参考并查集的模板,如果a和b已经在一个集合当中了,说明这两个点已经被一种方式连接起来了,
        如果加入a-b这条边,会导致集合中有环的生成,而树中不允许有环生成,所以一个连通块中的点的数量假设
        为x,那么里面x个节点应该是被串联起来的,有x-1条边,所以只有当a,b所属的集合不同时,才能将a-b这条
        边加入到总集合当中去
        */
        {
            p[find(a)]=p[find(b)];//将a,b所在的两个集合连接起来
            cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
            res+=w;//加入到集合中的边的权重之和
        }
    }

    if(cnt==n-1) return res;//可以生成最小生成树
    else return 0x3f3f3f3f;//树中有n个节点便有n-1条边,如果cnt不等于（小于）n-1的话,说明无法生成有n个节点的树，树不可连通
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++) p[i]=i;//初始化并查集

    for(int i=0;i<m;i++)//读入所有边
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }

    sort(edges,edges+m);//将边的权重按照大小一一排序

    int t=Kruskal();

    if(t==0x3f3f3f3f) printf("impossible\n");
    else printf("%d\n",t);

    return 0;
}