Algoritmia - ALGORTIMO DE KRUSKAL

#include <stdio.h>

#include <stdlib.h>

// Estructura para representar una arista

struct Edge {

    int src, dest, weight;

};

// Estructura para representar un conjunto disjunto

struct Subset {

    int parent;

    int rank;

};

// Función para encontrar el conjunto al que pertenece un elemento

int find(struct Subset subsets[], int i) {

    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, subsets[i].parent);

    return subsets[i].parent;

}

// Función para unir dos conjuntos en función de la clasificación por rango

void Union(struct Subset subsets[], int x, int y) {

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

    else {

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

    }

}

// Función principal del algoritmo de Kruskal

void KruskalMST(struct Edge edges[], int V, int E) {

    struct Subset *subsets = (struct Subset *)malloc(V * sizeof(struct Subset));

    for (int i = 0; i < V; i++) {

        subsets[i].parent = i;

        subsets[i].rank = 0;

    }

    qsort(edges, E, sizeof(edges[0]), [](const void *a, const void *b) -> int {

        return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;

    });

    struct Edge *result = (struct Edge *)malloc((V - 1) * sizeof(struct Edge));

    int e = 0;  // Índice del resultado, inicializado en 0

    for (int i = 0; e < V - 1 && i < E; i++) {

        struct Edge next_edge = edges[i];

        int x = find(subsets, next_edge.src);

        int y = find(subsets, next_edge.dest);

        if (x != y) {

            result[e++] = next_edge;

            Union(subsets, x, y);

        }

    }

    // Mostrar el resultado

    printf("Aristas seleccionadas en el árbol de expansión mínima:\n");

    for (int i = 0; i < e; i++)

        printf("(%d, %d) con peso %d\n", result[i].src, result[i].dest, result[i].weight);

    free(subsets);

    free(result);

}

// Programa principal

int main() {

    // Ejemplo de uso

    int V = 4;  // Número de vértices en el grafo

    int E = 5;  // Número de aristas en el grafo

    struct Edge edges[] = {

        {0, 1, 10},

        {0, 2, 6},

        {0, 3, 5},

        {1, 3, 15},

        {2, 3, 4},

    };

    KruskalMST(edges, V, E);

    return 0;

}