kruskal.cpp

// Author: Harsh Gupta
// Date: 12 November 2013
// Implementation of Kruskal algorithm to find the minimum spanning tree
// on a Undirected Graph

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

#define V 6 // Max Size of The Matrix
const float inf = 99999;

typedef struct edge{
    int to;
    int from;
    float weight;
}edge;

typedef struct graph{
    float adjmat[V][V];
    edge edges[V*V];
    int no_edges;
}graph;

graph init_graph(graph g);
/* float dist[V]; */

int is_empty(int A[], int size){
    int i;
    for(i=0;i<size;i++){
        if(A[i] != 0)
            return 0;
    }
    return 1;
}

graph add_edge(graph g, int i, int j, int cost){
    g.adjmat[i][j] = cost;
    g.adjmat[j][i] = cost;
    g.edges[g.no_edges].to= i;
    g.edges[g.no_edges].from= j;
    g.edges[g.no_edges].weight= cost;
    g.no_edges++;
    return g;
}

static int edge_comp(const void *a, const void *b){
    if(((edge*)a)->weight > ((edge*)b)->weight) return 1;
    else if(((edge*)a)->weight == ((edge*)b)->weight) return 0;
    else return -1;
}

graph sort_edges(graph g){
    qsort(g.edges, g.no_edges, sizeof(edge), edge_comp);
    return g;
}

void update_set(int A[], int size, int u, int v){
    int s_u = A[u];
    int s_v = A[v];
    for(int i=0;i<size;i++){
        if(A[i] == s_v) A[i] = s_u;
    }
}

graph Kruskal(graph g){
    graph A;
    A = init_graph(A);
    g = sort_edges(g);
    int set[V];
    /* int no_set=V; */
    for(int i = 0;i<V;i++) set[i] = i;
    // set represents the
    for(int i = 0;i<g.no_edges;i++){
        edge e = g.edges[i];
        int u = e.to;
        int v = e.from;
        float w = e.weight;
        if(set[u] != set[v]){
            update_set(set, V, u, v);
            A = add_edge(A, u, v, w);
            /* set[u] = set[v] */
        }
    }
    return A;
}

/* int min_dist_in_Q(int A[], int size){ */
/*     int i; */
/*     float min=inf; */
/*     int min_pos; */
/*     for(i=0;i<size;i++){ */
/*         if(dist[i] < min && A[i] == 1){ */
/*             min = dist[i]; */
/*             min_pos = i; */
/*         } */
/*     } */
/*     return min_pos; */
/* } */
/*  */
graph init_graph(graph g){
    g.no_edges = 0;
    for(int i=0;i<V*V;i++){
        g.edges[i].to = 0;
        g.edges[i].from = 0;
        g.edges[i].weight = inf;
    }
    printf("\n");
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            g.adjmat[i][j] = inf;
        }
    }
    return g;
}

void print_graph(graph g){
    for(int i=0;i<g.no_edges;i++){
        printf("(%d,%d,%.0f) ",g.edges[i].to,g.edges[i].from, g.edges[i].weight);
    }
    printf("\n");
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            float w = g.adjmat[i][j];
            if(w !=inf)
                printf("%.0f ",w);
            else
                printf("# ");
        }
        printf("\n");
    }
}

int main(){
    graph g;
    g = init_graph(g);
    printf("Enter a connected tree of size %d\n", V);
    int u, v;
    float w;
    printf("Enter the edges in from 'to from weight' ");
    printf("Enter 0 0 0 to terminate input \n");
    /* scanf("%d %d %f", &u, &v, &w); */
    scanf("%d",&u);
    scanf("%d",&v);
    scanf("%f",&w);
    while(u !=0 || v != 0){
        g = add_edge(g, u, v, w);
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%f",&w);
    }
    print_graph(g);

    graph A = Kruskal(g);
    printf("The minimum spanning tree is \n");
    print_graph(A);
    /* g = input_graph(g); */
    /* dijkstra(g, 0); */
    /* for(int i=0;i<V;i++){ */
    /*     printf("%f ", dist[i]); */
    /* } */

    printf("\n");
    return 0;
}