Kruskal算法使用详情

Kruskal算法，克鲁斯卡尔算法又称避圈法。

Kruskal算法主要是用来找无向图的最小生成树的 。

Kruskal算法的思想和步骤：

1.用结构体数组存储每条边的信息，并对数组按边的大小从小到大进行排序。

2.按照从小到大的顺序，依次将边加入到生成子图中，若加入该边会构成环，则不能加入该边；直至所有的点都已经被加入或者加入了n-1条边。

可以用反证法来证明一下Kruskal算法：

先考虑一条边不一样的情况：如果有更好的方案，与原方案只有一条边不一样。我们对边按从小到大的顺序编号，显然这条边比原方案同序号边的权值要小，但是根据克鲁斯卡尔算法的步骤，显然这是不成立的，因为比原方案同序号边的权值小的边都会与前面的边构成环。

然后考虑两条边的情况：如果有更好的方案，与原方案只有两条边不一样。1.如果这两条不同的边不相邻，和一条边情况一样，显然不成立。2.如果这两条边是相邻的，设其中一条边的序号为i，另一条为i+1，则有Ei+Ei+1

然后考虑多条边的情况：与上同。

代码示例：

#include 
#include 
#include 
#include 
using namespace std;
#define Max_point 100   //点
#define Max_edge 10000+5    //边

typedef struct Edges{  //定义结构体，存储边
    int s,e,v;
}Edges;

Edges Edge[Max_edge+5];
int s[Max_point];
int a,b,v,num,sum;


void init() //初始化数据
{
    a=b=v=-1;
    sum=0;
    return;
}
void input() //输入数据
{
    num=0;
    while(scanf("%d%d%d",&a,&b,&v))
    {
        if(a == 0&& b == 0&& v == 0)
            break;
        Edge[num].s = a;
        Edge[num].e = b;
        Edge[num].v = v;
        s[a] = a;
        s[b] = b;
        num++;
    }
    return;
}

bool cmp(Edges t1,Edges t2)
{
    if(t1.v<=t2.v)
        return true;
    else return false;
}

int find(int x) //并查集
{
    int r=x;
    while(r!=s[r])  //返回根节点
        r=s[r];
    while(s[x]!=r)
    {
        s[x]=r; //修改该节点对应的上节点
        x=s[x]; //返回上级节点
    }
    return r;
}
int main()
{
    init();
    input();
    sort(Edge,Edge+num,cmp);
    for(int i=0; it2)
            s[t1]=t2;
        else s[t2]=t1;
        sum += Edge[i].v;
        //printf("%d----%d----%d----%d------%d\n",Edge[i].s,Edge[i].e,t1,t2,Edge[i].v);
    }
    printf("%d\n",sum);
}

1 2 3
2 3 3
1 0 4
1 4 2
2 0 2
3 0 4
0 5 3
3 5 2
4 0 3
4 6 2
0 6 4
0 7 2
0 8 4
6 7 3
7 8 3
5 8 2
0 0 0
输出结果为18。