一个无向图，寻找最小代价生成树：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set> 
using namespace std;
struct edge{
    int fromvex;
    int endvex;
    int weight;
    edge(int fv,int ev,int we):fromvex(fv),endvex(ev),weight(we){}
};
bool compare(edge a,edge b)
{
    return a.weight<b.weight;    
}
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    for (auto& el : vec)
    {
        os << el << ' ';
    }
    return os;
}
std::ostream& operator<<(std::ostream& os, const edge & vec)
{
    os<<vec.fromvex<<" "<<vec.endvex<<" "<<vec.weight<<endl;
    return os;
}
int Kruscal()
{
    vector<edge> edgeInfo{edge(4,5,25),edge(0,5,23),
                      edge(3,4,20),edge(0,1,18),
                      edge(3,5,15),edge(1,5,12),
                      edge(2,3,10),edge(1,3,8),
                      edge(1,2,5),edge(0,4,4)};//unsorted graphic edgeset
    
    sort(begin(edgeInfo),end(edgeInfo),compare);//  sorted graphic edgeset by weight
    
    vector<edge> kruscal;
    vector<set<int>> connectedCom;//different connected component
    //init connected commponent
    //Total 6 graph vertices
    int vernumber = 6;
    for(int i = 0;i<vernumber;i++)
    {
        set<int> a{i};
        connectedCom.push_back(a);
    }
    
    int k = vernumber - 1;// k edge is needed in mininum cost spanning tree
    int index = 0;// which edge in sorted edge
    int m1 = 0,m2 = 0;
    while(k>0)
    {
        //serach edgeInfo[index].fromvex and endvex in different connectedCom
        for(size_t i = 0;i<connectedCom.size();i++)
        {
            for(int n:connectedCom[i])
            {
                if(n==edgeInfo[index].fromvex) m1 = i;
                if(n==edgeInfo[index].endvex)  m2 = i;
            }
        }   
        //if fromvex endvex is in different connectedCom
        if(m1!=m2)
        {
            kruscal.push_back(edgeInfo[index]);
            k--;
            for(int n:connectedCom[m1])
            {
                connectedCom[m2].insert(n);
            }
            //delete one of set<int> in connectedCom sets
            connectedCom[m1].clear();
        }
        //next edge 
        index++;
    }
    cout<<kruscal<<endl;
    return 0;
}
int main()
{
    Kruscal();
    return 0;
}

 结果：

1、今天重新复习了一下kruscal算法，并且使用了C++复现了算法过程。

2、对于最小生成树的算法还有prim算法。

3、重点在于：

（1）根据权重排序。

（2）判断新的edge的fromvex和endvex是否出现在同一个连通域里面。（每个连通域不能出现回路）

（3）每两个连通域合在一起，就要消除其中一个连通域。

kruscal算法是用于生成最小生成树的常见算法，最小生成树也就是在包含图中所有节点的树中，边权和最小的那棵树。基本实现方法如下：

1. 首先将所有的边从小到大排序；
2. 从小边一直搜索到大边，如果一条小边的两个端点，不属于同一个并查集，那么这条小边就是连接这两个集合的最优边，那么将这条小边加入最小生成树中，将两个并查集合并；
3. 将所有的边搜索完成，就得到了连通所有节点的最小生成树。
   示例如下：
   

/*利用kruscal算法得到最小生成树，即生成树中边权和最小的树*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

int nump;  //村庄数目
struct edge{
    int a,b;
    int len;
}e[200];
int tree[200];
int ans;

int findroot(int x)
{
    if(tree[x]==-1){
        return x;
    }else{
        int tmp = findroot(tree[x]);
        tree[x] = tmp;
        return tmp;
    }
}

bool cmp(edge a,edge b)
{
    return a.len<b.len;
}

int main()
{
    memset(tree,-1,sizeof(tree));

    while(scanf("%d",&nump)!=EOF && nump!=0){
        int numedge = nump * (nump-1) /2;
        int a=0; int b=0; int len=0;
        for(int i=0;i<numedge;i++){
            scanf("%d %d %d",&a,&b,&len);
            e[i].a = a;
            e[i].b = b;
            e[i].len = len;
        }

        sort(e,e+numedge,cmp);  //将各条边按照从小到大的顺序排列

        for(int i=0;i<numedge;i++){
            int a = e[i].a;
            int b = e[i].b;
            a = findroot(a);
            b = findroot(b);
            if(a!=b){  //如果边的两个点不在同一个并查集中，则连接
                tree[a] = b;
                ans+=e[i].len;
            }
        }

        cout<<ans<<endl;
    }
}

/*
输入示例：
3
1 2 1
1 3 2
2 3 4
输出：
3
*/

kruscal算法

最小生成树：无向连通图中边权和最小的生成树。
kruscal算法：
1、基本思想：贪心思想，按照边权升序排序；
2、按照边权从小到大枚举边，然后每次每次判断枚举的边所连接的两点是否已经联通，如果已经联通，则跳过这条边，否则将这条边算入最小生成树，并将两个点所在的集合联通。

其中判断是否联通以及合并操作，可以用数据结构并查集来维护。
模板：

struct node{int u,v,w;}e[N];
bool cmp(node a,node b){return a.w<b.w;}
int f[N],n,m;
int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) 
          scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+1+m,cmp);
    ll ans=0;int cnt=0;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        int x=getf(e[i].u);   
        int y=getf(e[i].v);
        if(x==y)   continue;
        f[x]=y;  
        ans+=e[i].w;
        cnt++;
        if(cnt==n-1)   break;//已经完全联通直接break，小小的剪枝
    }
    printf("%lld\n",ans);
    return 0;
}

例：问题 F: 修建道路 (roads)

题目描述
Farmer John 最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达 （也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。

所有N(1≤N≤1000个农场（用1…N顺次编号）在地图上都表示为坐标为(Xi,Yi)的点(0≤Xi≤1000000,0≤Yi≤1000000），两个农场间道路的长度自然就是代表它们的点之间的距离。

现在 Farmer John 也告诉了你农场间原有的M(1≤M≤1000条路分别连接了哪两个农场， 他希望你计算一下，为了使得所有农场连通，他所需建造道路的最小总长是多少。

输入
第 1行: 2个用空格隔开的整数：N和 M
第2…N+1 行：第i+1行为2个用空格隔开的整数：Xi，Yi
第N+2…N+M+1行：每行用2个以空格隔开的整数i、j描述了一条已有的道路，这条道路连接了农场i和农场j

输出
第1行：输出使所有农场连通所需建设道路的最小总长，保留2位小数，不必做任何额外的取整操作。为了避免精度误差，计算农场间距离及答案时，请使用64位实型变量。
样例输入
4 1
1 1
3 1
2 3
4 3
1 4
样例输出
4.00

提示
样例解释：
FJ 一共有4个坐标分别为$(1,1),(3,1),(2,3),(4,3)$的农场。农场1和农场4之间原本就有道路相连。
FJ 选择在农场1和农场2 间建一条长度为2.00的道路，在农场3和农场4间建一条长度为2.00的道路。这样，所建道路的总长为4.00，并且这是所有方案中道路总长最小的一种。

对于所有的数据，1≤N,M≤1000,0≤Xi，Yi≤1000000。
题意：
给出n个点的坐标$（x,y）$，给出m个已经连通的点对，求最小生成树。
注意题目高光提示。

wa的几个点：
在建图求两点之间的距离的时候，必须要先进行int->double转换。
并查集维护的是n个点，构建边的结构体要用到点的结构体。

#include <bits/stdc++.h>
#include <cstdio>
//#define local
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int N = 1005;
const int inf = 0x3f3f3f3f;
const int mod = 1e8+7;
int n,m;
int f[N];

struct Point
{
    int x,y,z;
} a[N];
struct node
{
    Point c,d;
    double len;
}e[N*N];

bool cmp(node a,node b)
{
    return a.len<b.len;
}
int getf(int x)
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
#ifdef local
    freopen("input.txt","r",stdin);
#endif // local
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d%d",&a[i].x,&a[i].y),a[i].z=i;
    for(int i=1; i<=n; i++)
        f[i]=i;
    while(m--)
    {
        int i,j;
        scanf("%d%d",&i,&j);
        int fi=getf(i);
        int fj=getf(j);
        if(fi!=fj)
            f[fi]=fj;
    }
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i!=j)
            {
                cnt++;
                e[cnt].c=a[i],e[cnt].d=a[j];
                double x1=(double)(a[i].x-a[j].x);
                double y1=(double)(a[i].y-a[j].y);
                e[cnt].len=sqrt(x1*x1+y1*y1);
            }
        }
    }
    sort(e+1,e+cnt+1,cmp);
    double ans=0;
    for(int i=1; i<=cnt; i++)
    {
        int fc=getf(e[i].c.z);
        int fd=getf(e[i].d.z);
        if(fc!=fd)
            ans+=e[i].len,f[fc]=fd;
    }
    printf("%.2f",ans);
    return 0;
}