标题：Kruskal贪心算法求最小生成树
出处：Felix021
时间：Sat, 07 Nov 2009 02:35:25 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1756

内容：
#include <stdio.h>
#include <stdlib.h>

/*
* Kruskal贪心算法求最小生成树(heap+并查集)
* 测试输入数据：

6 10 //6个顶点10条边
1 5 2  //从顶点1到顶点5的边权重为2
2 4 3
4 5 1
0 3 6
2 3 7
5 2 6
4 0 7
1 3 5
1 2 4
3 5 9

*/

struct edge {
    int start, end, weight;
};

void siftdown (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i * 2 <= n) {
        i *= 2;
        if (i + 1 <= n && a[i].weight > a[i + 1].weight) i++;
        if (a[i].weight < a[i/2].weight ) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
    }
}

void siftup (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i > 1) {
        if (a[i].weight < a[i/2].weight) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
        i /= 2;
    }
}

void makeheap(struct edge *a, int n) {
    int i;
    for (i = n / 2; i >= 1; --i) {
        siftdown(a, n, i);
    }
}

struct edge pop(struct edge *a, int *n) {
    struct edge t;
    t = a[1];
    a[1] = a[*n];
    (*n)--; //第二次挂在这里，不能写*n--(*n; n-=1;), 要写(*n)--
    siftdown(a, *n, 1);
    return t;
}

void dump(struct edge *a, int n) {
    int i;
    for (i = 0; i < n; ++i) {
        printf("edge (%d, %d), %d\n", a[i].start, a[i].end, a[i].weight);
    }
}

void initUnionSet(int a[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = i;
    }
}

int getFather(int a[], int x) {
    return a[x] == x ? x : (a[x] = getFather(a, a[x]));
}

void merge(int a[], int x, int y) {
    x = getFather(a, x);
    y = getFather(a, y);
    a[x] = y;
}

int haveCommonAncestor(int a[], int x, int y) {
    return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}


int main () {
    int m, n, i, k, *father;
    struct edge *input, *output, t;

    scanf("%d%d", &m, &n);
    input = (struct edge *)malloc(sizeof(struct edge) * (n + 1));
    for (i = 1; i <= n; ++i) {
        scanf("%d%d%d", &input[i].start, &input[i].end, &input[i].weight);
    }
    makeheap(input, n);
    dump(input+1, n);
    printf("end input\n");
    
    int n1 = n;
    output = (struct edge *)malloc(sizeof(struct edge) * (m - 1));
    father = (int *)malloc(sizeof(int) * n);
    initUnionSet(father, m);
    k = 0;
    printf("\nStart:\n");
    while (n1 > 0) {
        t = pop(input, &n1);
        printf("edge (%d,%d), %d ", t.start, t.end, t.weight);
        if (0 == haveCommonAncestor(father, t.start, t.end)) {
            printf("added in\n");
            output[k] = t;
            k++;
            merge(father, t.start, t.end);
            if (k == m - 1) {
                printf("~~ok~~\n");
                break;
            }
        }
        else {
            printf("ignored\n");
        }
    }
    printf("\nresult:\n");
    dump(output, k);

    free(input);
    free(output);
    free(father);
    return 0;
}


注：下面这段代码是之前写的，写了一个简单的链表+插入来实现，本来是想用队列式链表然后再排序的，但是太麻烦了，干脆直接插入排序，所以那个tail也就一点用也没有了（用在tree那个list里看起来还更NC）。其实更好的办法应该是根据输入的n动态分配足够的空间，全部输入以后然后用heap或者用qsort。


#include <stdio.h>
#include <stdlib.h>

/*
 * Kruskal贪心算法求最小生成树
 * 测试输入数据：
    6 10 //6个顶点10条边
    1 5 2  //从顶点1到顶点5的边权重为2
    2 4 3
    4 5 1
    0 3 6
    2 3 7
    5 2 6
    4 0 7
    1 3 5
    1 2 4
    3 5 9
 */

//链表
struct edge {
    int start, end, weight;
    struct edge *next;
};

struct linklist {
    struct edge *head, *tail;
};


void initLinkList(struct linklist *p) {
    p->head = (struct edge *) malloc(sizeof(struct edge));
    p->head->next = NULL;
    p->tail = p->head;
}

void insert(struct linklist *p, struct edge e) {
    struct edge *q = p->head, *t;
    while (q->next != NULL) {
        if (q->next->weight > e.weight) {
            break;
        }
        q = q->next;
    }
    t = (struct edge *) malloc(sizeof(struct edge));
    *t = e;
    t->next = q->next;
    q->next = t;
    if (t->next == NULL) {
        p->tail = t;
    }
}

void dump(struct linklist *p) {
    struct edge *q = p->head->next;
    while (q != NULL) {
        printf("q = %p, ", q);
        printf("edge (%d, %d), %d\n", q->start, q->end, q->weight);
        q = q->next;
    }
}

//并查集
void initUnionSet(int a[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = i;
    }
}

int getFather(int a[], int x) {
    if (a[x] == x) {
        return x;
    }
    else {
        a[x] = getFather(a, a[x]);
        return a[x];
    }
}

void merge(int a[], int x, int y) {
    x = getFather(a, x);
    y = getFather(a, y);
    a[x] = y;
}

int haveCommonAncestor(int a[], int x, int y) {
    return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}

int main () {
    int m, n; //m点，n边
    int i;
    struct linklist edges, tree;
    struct edge t;
    int father[1000];
    initLinkList(&edges);
    initLinkList(&tree);

    scanf("%d%d", &m, &n);
    for (i = 0; i < n; ++i) {
        scanf("%d%d%d", &t.start, &t.end, &t.weight);
        insert(&edges, t);
    }
    printf("Input:\n");
    dump(&edges);

    struct edge *p = edges.head->next;
    printf("\nBuilding tree...\n");
    initUnionSet(father, m);
    int count = 0;
    while (p != NULL) {
        printf("p = %p, ", p);
        printf("edge (%d, %d), %d: ", p->start, p->end, p->weight);
        if (0 == haveCommonAncestor(father, p->start, p->end)) {
            printf("added in.\n");
            insert(&tree, *p);
            merge(father, p->start, p->end);
            count++;
            printf("count = %d\n", count);
            if (count == m - 1) {
                break;
            }
        }
        else {
            printf("ignored.\n");
        }
        p = p->next;
    }

    printf("\nFinal result:\n");
    dump(&tree);
    return 0;
}



Generated by Bo-blog 2.1.0