kruskal算法2

 

/*
  很久以前写过一个，很久没用了，发现看不太懂了，现在重新学习，重新写过。跟以前的不太一样，好像比较简单。以后就记住这个了。
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define N 101
#define M N*2-1

struct node
{
    int x;
    int y;
    int w;
}edge[M]; //边集

int p[M], rank[M];
int sum;

int cmp(const void *p, const void *q)
{
    return ((struct node *)p)->w > ((struct node *)q)->w ? 1 : -1;
}

/* 查找x元素所在的集合,用到压缩路径 */
int find(int x)
{
    int y, z;
    y = x;
    while(p[y] != y)
        y = p[y];
    while(x != y)
    {
        z = p[x];
        p[x] = y;
        x = z;
    }
    return y;
}


/*合并x和y*/
void _union(struct node e)
{
    int x, y;

    x = find(e.x); //找到祖先节点
    y = find(e.y);
    if(x!=y) //如果不在一个集合里

    {
        printf("%d--%d %d\n", e.x, e.y, e.w);
        if(rank[x] > rank[y]) //小秩树放在大秩树下面
        {
            p[y] = x;
        }
        else
        {
            if(rank[x] == rank[y])
                rank[y]++;
            p[x] = y;
        }
        sum += e.w; //权相加
    }
}

int main()
{
    int i, j, k;
    int n;

    freopen("in.txt", "r", stdin);
    scanf("%d", &n); //输入n条边

    for(i=0; i<n; i++)
    {
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
        p[edge[i].x] = edge[i].x;   //初始化每个节点的父节点为其本身

        p[edge[i].y] = edge[i].y;  

        rank[edge[i].x] = rank[edge[i].y] = 0;  //秩
    }

    qsort(edge, n, sizeof(edge[0]), cmp); //按权值非降序排序

    sum = 0;
    for(i=0; i<n; i++)
    {
        _union(edge[i]); //处理每条边
    }
    printf("%d\n", sum);

    getch();
    return 0;
}