c - 克鲁斯卡尔算法(集合除法)

Question

我在理解 Kruskal 算法时遇到问题。这是代码

#include <stdio.h>
#define MAX_VERTICLES 100
#define INF 1000

int parent[MAX_VERTICLES];
int num[MAX_VERTICLES];

void setInit(int n) {
    int i;
    for (i = 0; i < n; i++) {
        parent[i] = -1;
        num[i] = 1;
    }
}

int setFind(int vertex) {
    int p, s, i = -1;
    for (i = vertex;(p = parent[i]) >= 0; i = p)
        ;
    s = i;
    for (i = vertex;(p = parent[i]) >= 0; i=p)
        parent[i]=s;
    return s;
}

void setUnion(int s1, int s2) {
    if (num[s1] < num[s2]) {
        parent[s1]=s2;
        num[s2]+=num[s1];
    }
    else {
        parent[s2] = s1;
        num[s1] += num[s2];
    }
}

typedef struct {
    int key;
    int u;
    int v;
}element;

#define MAX_ELEMENT 100
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;

void init(HeapType *h) {
    h->heap_size = 0;
}

void printHeap(HeapType *h) {
    int i;
    int level = 1;
    printf("\n==========");
    for (i = 1; i <= h->heap_size;i++) {
        if (i = level) {
            printf("\n");
            level *= 2;
        }
        printf("\t%d", h->heap[i].key);
    }
    printf("\n==========");
}

void insertMinHeap(HeapType *h, element item) {
    int i;
    i = ++(h->heap_size);
    while ((i != 1) && (item.key < h->heap[i / 2].key)){
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item;
}

element deleteMinHeap(HeapType *h) {
    int parent, child;
    element item, temp;
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
    while (child <= h->heap_size) {
        if ((child < h->heap_size) && (h->heap[child].key > h->heap[child + 1].key))
            child++;
        if (temp.key <= h->heap[child].key) break;
        h->heap[parent] = h->heap[child];
        parent = child;
        child *=2;
    }
    h->heap[parent] = temp;
    return item;
}

void insertHeapEdge(HeapType *h, int u, int v, int weight) {
    element e;
    e.u = u;
    e.v = v;
    e.key = weight;
    insertMinHeap(h, e);
}

void insertAllEdges(HeapType *h){
    insertHeapEdge(h, 0, 1, 13);
    insertHeapEdge(h, 1, 2, 36);
    insertHeapEdge(h, 2, 3, 12);
    insertHeapEdge(h, 2, 4, 28);
    insertHeapEdge(h, 3, 5, 32);
    insertHeapEdge(h, 4, 5, 14);
    insertHeapEdge(h, 0, 5, 19);
    insertHeapEdge(h, 0, 6, 23);
    insertHeapEdge(h, 1, 6, 15);
    insertHeapEdge(h, 5, 6, 20);
}

void kruskal(int n) {
    int edge_accepted = 0;
    HeapType h;
    int uset, vset;
    element e;

    init(&h);
    insertAllEdges(&h);
    setInit(n);
    while (edge_accepted<(n-1)){
        e = deleteMinHeap(&h);
        uset = setFind(e.u);
        vset = setFind(e.v);
        if (uset != vset) {
            printf("(%d,%d) %d \n", e.u, e.v, e.key);
            edge_accepted++;
            setUnion(uset, vset);
        }7
    }
}

void main(){
    kruskal(7);

    getchar();
}

我无法理解 setFind 和 setUnion 函数如何工作。(其他都很好)

有人可以明确解释这些算法吗？

Answer 1

Kruskal 的算法(旨在生成最小生成树)需要子例程来查找给定顶点的连通分量以及合并连通分量的可能性。

显然，parent[i] 存储一个可以跟踪的单个顶点，直到没有父节点为止；通过这种方式到达的节点是连接组件的根 - 可以通过 setFind 找到该节点； num[i] 表示此关系定义的子项数量。因此，连接的组件被隐式地表示。

函数setUnion旨在通过将一个连接组件的根附加到另一组件的根并更新子组件的数量，将较小的连接组件合并到较大的连接组件中。