kruskal 算法

//终于自己搞出来了，最小生成树的kruskal算法
#include <stdio.h>
#include <stdlib.h>
#define inf 100000
#define N 20   //顶点数
#define M N*2-1   //边数

typedef struct
{
    char a;
    char b;
    int weight;
}edgenode;   

edgenode graph[M];

int parent[N];


/*并查集的两个算法*/
int find(int x)
{
    if(parent[x] < 0)
        return x;
    else return find(parent[x]);
}

int _find(int x) //压缩路径的find（）

{
    int y,z;
    y = x;
    while(parent[y] >= 0)
        y = parent[y];
    while(x != y)
    {
        z = parent[x];
        parent[x] = y;
        x = z;
    }
    return y;
}

void _union(int a, int b)   //合并
{
    int weight = parent[a] + parent[b];

    //weight 放的是两个数节点和的负值


    if(parent[a] < parent[b])   //节点数多的数的根作为另一棵树的根
    {
        parent[b] = a;
        parent[a] = weight;
    }
    else
    {
        parent[a] = b;
        parent[b] = weight;
    }
}


/*核心算法：kruskal*/
int kruskal(int n, int m) //n条边，m个顶点

{
    int i, total, x, y;
    
    for(i=0; i<m; i++)
    {
        parent[i] = -1;
    }

//处理第一条最小边
    parent[graph[0].a - 'A'] = -2;
    parent[graph[0].b-'A'] = 0;
    total = graph[0].weight;   
    printf("%c--%c:%d\n", graph[0].a, graph[0].b, graph[0].weight);
    for(i=1; i<n; i++)
    {
            x = _find(graph[i].a - 'A');
            y = _find(graph[i].b - 'A');
            if(x!=y)
            {
                _union(x, y);
                printf("%c--%c:%d\n", graph[i].a, graph[i].b, graph[i].weight);
                total += graph[i].weight;
            }
    }
    return total;        
}

int cmp(const void *p, const void *q)
{
    edgenode *a = (edgenode *)p;
    edgenode *b = (edgenode *)q;
    return a->weight > b->weight ? 1 : -1;
}

int main()
{
    int k, m, n;
    int weight;

    freopen("prim.dat", "r", stdin);
    scanf("%d %d", &m, &n); //m 个顶点，n条边

    getchar();

    for(k=0; k<n; k++)
    {
        scanf("%c %c%d", &graph[k].a, &graph[k].b, &graph[k].weight);
        getchar();
    }
    qsort(graph, n, sizeof(graph[0]), cmp);    //按权值从小到大排序
    weight = kruskal(n, m);
    printf("total weight:%d\n", weight);
}