最小生成树–kruskal

也加克鲁斯卡尔算法。

kruskal算法的思想简单说来就是：每次选择图中最小边权的边，如果边两端的顶点在不同的连通块中，就把这条边加入最小生成树中。

如果是稠密图（边多），用prim算法；如果是稀疏图（边少），用kruskal算法，或者用我自己想的“做减法”。

//对于kruskal算法来说，由于需要判断边的两个端点
//是否在不同的连通块中，因此边的两个端点的编号是一定
//需要的；而算法中有涉及边权，因此边权也必须要有

struct edge{

    //边的两个端点编号 
    int u,v;

    //边权 
    int cost; 

}E[MAXE]; 



//需要写一个排序函数来让数组E按边权从小到大排序，
//因此可以自定义sort的cmp函数

bool cmp(edge a,edge b) 
{

    return a.cost<b.cost;

}



//kruskal算法伪代码模板


int kruskal() 
{
    令最小生成树的边权之和为ans、最小生成树的当前边数 num_edge;

    将所有边按边权从小到大排序;

    for( 从小到大枚举所有边  ) 
    {
        if( 当前测试边的两个端点在不同的连通块中  )
        {
            将该测试边加入最小生成树中;

            ans+=测试边的边权;

            最小生成树的当前边数num_edge+1;

            当边数num_edge等于顶点数-1时结束循环; 


        }



    }





}




//伪代码中两处地方很不直观
//1.如何判断测试边的两个端点是否在不同的连通块中；
//2.如何将测试边加入最小生成树

输入

6 10
0 1 4
0 4 1
0 5 2
1 2 1
1 5 3
2 3 6
2 5 5
3 4 5
3 5 4
4 5 3

输出

11



  //以上问题需要用到并查集，下面 提供kruskal算法实际应用例程 #include <cstdio>  #include <algorithm> using namespace std; const int MAXV=110; const int MAXE=10010; //边集定义部分 struct edge{ //边的两个端点编号  int u,v; //边权 int cost; }E[MAXE]; bool cmp(edge a,edge b) { return a.cost<b.cost; } //并查集部分 //并查集数组  int father[MAXV]; //并查集查询函数 int find_father(int x) { int a=x; while(x!=father[x]) { x=father[x]; } //路径压缩 while( a!=father[a] ) { int z=a; a=father[a]; father[z]=x; } return x; } //kruskal 部分，返回最小生成树的边权之和，参数n为顶点个数， //m为图的边数 int kruskal(int n,int m) { //ans 为边权之和，num_edge为当前生成树的边数 int ans=0; int num_edge=0; for(int i=0;i<n;i++) { //初始化并查集  father[i]=i; } //所有边权按边权从小到大排序  sort(E,E+m,cmp); for(int i=0;i<m;i++) { //查询测试边两个端点所在集合的根结点  int fau=find_father(E[i].u); int fav=find_father(E[i].v); //如果不在一个集合中  if( fau!=fav ) { father[fau]=fav; //合并集合（就是把测试边加入到最小生成树中）  //边权之和增加测试边的边权  ans+=E[i].cost; //当前生成树的边树加1  num_edge++; //边树等于顶点数减1时结束算法  if( num_edge == n-1 ) { break; } } } //无法连通时返回-1  if( num_edge !=n-1 ) { return -1; } else { //返回最小生成数的边权之和  return ans; } } int main() { int n,m; //顶点数、边数  scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { //两个端点编号，边权  scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost); } int ans= kruskal(n,m); printf("%d\n",ans); return 0; }