C语言 克鲁斯卡尔算法代码

以下是C语言实现的克鲁斯卡尔算法代码：

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

#define MAX_EDGE 20
#define MAX_VERT 20

typedef struct edge {
    int u, v, weight;
} edge;

typedef struct graph {
    edge edges[MAX_EDGE];
    int parent[MAX_VERT];
    int n, e;
} graph;

void init_graph(graph *g)
{
    g->n = 0;
    g->e = 0;
}

void add_edge(graph *g, int u, int v, int weight)
{
    g->edges[g->e].u = u;
    g->edges[g->e].v = v;
    g->edges[g->e].weight = weight;
    g->e++;
}

int find_parent(int parent[], int i)
{
    if (parent[i] == -1) {
        return i;
    }
    return find_parent(parent, parent[i]);
}

void union_set(int parent[], int x, int y)
{
    int xset = find_parent(parent, x);
    int yset = find_parent(parent, y);
    parent[xset] = yset;
}

int compare_edges(const void *a, const void *b)
{
    edge *a1 = (edge *) a;
    edge *b1 = (edge *) b;
    return a1->weight > b1->weight;
}

void kruskal(graph *g)
{
    int i, j, x, y;
    int parent[MAX_VERT] = {-1,};
    qsort(g->edges, g->e, sizeof(g->edges[0]), compare_edges);
    for (i = 0; i < g->e; i++) {
        x = find_parent(parent, g->edges[i].u);
        y = find_parent(parent, g->edges[i].v);
        if (x != y) {
            printf("%d - %d\n", g->edges[i].u, g->edges[i].v);
            union_set(parent, x, y);
        }
    }
}

int main()
{
    graph g;
    init_graph(&g);
    add_edge(&g, 0, 1, 10);
    add_edge(&g, 0, 2, 6);
    add_edge(&g, 0, 3, 5);
    add_edge(&g, 1, 3, 15);
    add_edge(&g, 2, 3, 4);
    kruskal(&g);
    return 0;
}

这里实现了一个简单的图数据结构，包含了边和顶点数量，以及边的集合和父节点数组。kruskal函数是主要的算法实现，它根据边的权值排序，然后检查每条边是否会形成环路，如果不会，就加入最小生成树。在这个例子中，我们创建了一个简单的无向加权图，并使用克鲁斯卡尔算法计算最小生成树。